P1345 [USACO5.4]奶牛的电信Telecowmunication 题解

一、题目描述：

　　n 个点，m 条边，给定起点 s 和终点 t ，求最少删去几个点后，s 和 t 不连通。

　　注意，s 和 t 不能删掉。1<=n<=100，1<=m<=600;

 二、解题思路：

　　刚刚学了最大费用流，知道最大流等于最小割。但此题割的不是边，是点。

　　我们需要将将割点转化为割边。把一个点切成两半！

　　为之奈何？把一个点看成两个点，不就可以切成两半了吗?

　　将每个点 i 与 i+n 连边，做到不重不漏。然后跑 EK 。

　　怎么证明割 i 与 i+n 之间的边时，方案一定最优呢？

　　感性理解：如果割的是其他的边，那么不会比割一个这条边连接的顶点划算；

　　所以割顶点一定是最划算的，也就是割 i 与 i+n 之间的边是最优的。

　　还有一个问题，网络流中是有边权的，这个题我们怎么设置边权呢？

　　假设割掉 x 条边，那么答案应该是 x，x = x*1 。

　　所以正向边权设为 1 就好了，反向边权设为 0 。

　　EK 的时间复杂度为 O(NW) ，这个题最多割 n 条边，时间复杂度最坏 O(N^2) ，绰绰有余。

　　其他没什么了，注意 dfs 起点设置为 s+n ，否则答案永远都是 1 ！

 三、完整代码：

 1 #include<iostream>
 2 #define N 220
 3 #define M 610
 4 using namespace std;
 5 int n,m,s,t,u1,v1,ans,vis[N];
 6 struct EDGE{
 7     int v,w,nxt;
 8 }edge[M*4+N*2];
 9 int head[N],cnt;
10 void add(int u,int v,int w)
11 {
12     edge[cnt].v=v;
13     edge[cnt].w=w;
14     edge[cnt].nxt=head[u];
15     head[u]=cnt;cnt++;
16 }
17 int dfs(int u)
18 {
19     if(u==t)    return 1;
20     if(vis[u])    return 0;    vis[u]=1;
21     for(int i=head[u];i!=-1;i=edge[i].nxt)
22         if(edge[i].w&&dfs(edge[i].v))
23         {
24             edge[i].w--;
25             edge[i^1].w++;
26             return 1;
27         }
28     return 0;
29 }
30 int EK()
31 {
32     for(int i=1;i<=n*2;i++)
33         vis[i]=0;
34     return dfs(s+n);
35 }
36 int main()
37 {
38     cin>>n>>m>>s>>t;
39     for(int i=1;i<=n*2;i++)
40         head[i]=-1;
41     for(int i=1;i<=n;i++)
42         add(i,i+n,1),add(i+n,i,0);
43     for(int i=1;i<=m;i++)
44     {
45         cin>>u1>>v1;
46         add(u1+n,v1,1),add(v1,u1+n,0);
47         add(v1+n,u1,1),add(u1,v1+n,0);
48     }
49     while(EK())    ans++;
50     cout<<ans<<'\n';
51     return 0;
52 }

 四、写题心得：

　　这个题有两个难点 ( 如果用我的方法做 ) ，一是拆点，二是设置边权。不过想出来了，就很高兴。加油！拜拜！