一、题目描述：
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 }
四、写题心得：
这个题有两个难点 ( 如果用我的方法做 ) ，一是拆点，二是设置边权。不过想出来了，就很高兴。加油！拜拜！