1574: [Usaco2009 Jan]地震损坏Damage
1574: [Usaco2009 Jan]地震损坏Damage
1574: [Usaco2009 Jan]地震损坏Damage
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 425 Solved: 232
Description
农夫John的农场遭受了一场地震.有一些牛棚遭到了损坏,但幸运地,所有牛棚间的路经都还能使用. FJ的农场有P(1 <= P <= 30,000)个牛棚,编号1..P. C(1 <= C <= 100,000)条双向路经联接这些牛棚,编号为1..C. 路经i连接牛棚a_i和b_i (1 <= a_i<= P;1 <= b_i <= P).路经可能连接a_i到它自己,两个牛棚之间可能有多条路经.农庄在编号为1的牛棚. N (1 <= N <= P)头在不同牛棚的牛通过手机短信report_j(2 <= report_j <= P)告诉FJ它们的牛棚(report_j)没有损坏,但是它们无法通过路经和没有损坏的牛棚回到到农场. 当FJ接到所有短信之后,找出最小的不可能回到农庄的牛棚数目.这个数目包括损坏的牛棚. 注意:前50次提交将提供在一些测试数据上的运行结果.
Input
* 第1行: 三个空格分开的数: P, C, 和 N
* 第2..C+1行: 每行两个空格分开的数: a_i 和 b_i * 第C+2..C+N+1行: 每行一个数: report_j
Output
* 第1行: 一个数,最少不能回到农庄的牛的数目(包括损坏的牛棚).
Sample Input
4 3 1 1 2 2 3 3 4 3
Sample Output
3
HINT
牛棚2遭到损坏,导致牛棚2, 3, 4里面的牛无法回到农庄.
Source
题解：一开始看到损坏什么的就想到割，然后就忍不住往最大流最小割上面想，事实证明我想多了。。。TT
一道搜索题，对于被割断的点最少的情况下，一定是损坏的牛棚刚刚好可以把那些发了短信的点包围导致其无法连通至1，然后根据这样子的情况来求出一个最优的切割情况，然后直接DFS出最优切割情况下仍然连通的点数，然后用N减一下完事。。
1 type
2 point=^node;
3 node=record
4 g:longint;
5 next:point;
6 end;
7 var
8 i,j,k,l,m,n,t,ans:longint;
9 a:array[0..100000] of point;
10 b,c,d:array[0..100000] of longint;
11 p:point;
12 procedure add(x,y:longint);inline;
13 var p:point;
14 begin
15 new(p);p^.g:=y;p^.next:=a[x];a[x]:=p;
16 end;
17 procedure dfs(x:longint);inline;
18 var p:point;
19 begin
20 if b[x]<>0 then exit;
21 inc(ans);b[x]:=1;
22 p:=a[x];
23 while p<>nil do
24 begin
25 if b[p^.g]=0 then dfs(p^.g);
26 p:=p^.next;
27 end;
28 end;
29 begin
30 readln(n,m,t);
31 for i:=1 to n do a[i]:=nil;
32 for i:=1 to m do
33 begin
34 readln(j,k);
35 add(j,k);add(k,j);
36 end;
37 fillchar(b,sizeof(b),0);
38 for i:=1 to t do
39 begin
40 readln(j);
41 b[j]:=1;
42 p:=a[j];
43 while p<>nil do
44 begin
45 if b[p^.g]=0 then b[p^.g]:=-1;
46 p:=p^.next;
47 end;
48 end;
49 for i:=1 to n do if b[i]=1 then b[i]:=-1;
50 ans:=0;
51 dfs(1);
52 writeln(n-ans);
53 end.