【题解】P7687 [CEOI2005] Critical Network Lines

· · 题解

这道题和求普通的割边十分相似。最开始的思路就是将 a 和 b 的情况分别求解，然后再进行合并，然而这样并不行。

本题的关键通信线路和割边并不是充要条件，而是充分不必要条件。有些边虽然是割边，但该边将所有点分为两部分后每部分均有 A 与 B，因此并不是关键通信线路。以 A 为例，若某条割边是关键通信线路，则必有一部分全是 A，另一部分没有 A，B 同理。而统计子树中含有 A,B 的结点数也十分容易，和求子树大小类似，通过递归不断累加即可。

和求普通的割边唯一不同的代码在于判断是否为特殊边时，再加上 !a[v] || a[v] == k || !b[v] || b[v] == l 关于 A,B 数量的判断就行了。由于有 \texttt{Special Judge} 的设置，在答案累加的同时直接用一个 pair 记录该边相邻的两个结点就行了。

代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 1e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int n,m,k,l,cnt,times,ans;
int dfn[MAX],low[MAX],a[MAX],b[MAX];
int head[MAX * 20],to[MAX * 20],nxt[MAX * 20];
pair <int,int> edge[MAX];
void add (int u,int v); 
void tarjan (int u,int fa);
int main ()
{
    //freopen (".in","r",stdin);
    //freopen (".out","w",stdout);
    n = read ();m = read ();k = read ();l = read ();
    for (int i = 1;i <= k;++i) a[read ()] = 1;
    for (int i = 1;i <= l;++i) b[read ()] = 1;
    for (int i = 1;i <= m;++i)
    {
        int x = read (),y = read ();
        add (x,y);add (y,x);
    } 
    tarjan (1,0);
    printf ("%d\n",ans);
    for (int i = 1;i <= ans;++i) printf ("%d %d\n",edge[i].first,edge[i].second);
    return 0;
}
inline int read ()
{
    int s = 0;int f = 1;
    char ch = getchar ();
    while ((ch < '0' || ch > '9') && ch != EOF)
    {
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar ();
    }
    return s * f;
}
void add (int u,int v)
{
    to[++cnt] = v;
    nxt[cnt] = head[u];
    head[u] = cnt;
}
void tarjan (int u,int fa)
{
    dfn[u] = low[u] = ++times;
    for (int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        if (!dfn[v])
        {
            tarjan (v,u);
            low[u] = min (low[u],low[v]);
            if (low[v] > dfn[u] && (!a[v] || a[v] == k || !b[v] || b[v] == l)) edge[++ans] = make_pair (u,v);//唯一不同的地方在这里
            a[u] += a[v],b[u] += b[v];//递归累加的过程
        }
        else if (v != fa) low[u] = min (low[u],dfn[v]);
    }
}