题解：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 记录该边相邻的两个结点就行了。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| #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 ()
{
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]);
}
}
|
