题意：
就在一个给定的无向图中至少应该去掉几个顶点才能使得s和t不联通。
算法：
如果s和t直接相连输出no answer。
把每个点拆成两个点v和v‘‘，这两个点之间连一条权值为1的边（残余容量）
v和v‘‘分别是一个流进的点，一个流出的点。
根据求最小割的性质，权值小的边是可能被选择的（断开的）。
添加源点st=0和汇点en=2*n+1，源点与s连权值为inf的边，t‘‘与汇点连权值为inf的边。
s与s‘‘，t与t‘‘连权值为inf的边，这样保证自己和自己是不会失去联系的。
如果i和j有边相连，则i‘‘和j连权值为inf的边，j‘‘与i连权值为inf的边。
这样建图后跑最大流，求得的流量即为点的个数。
然后编号从小到大枚举每个点，尝试去掉这个点（即只进不出），重新建图再跑最大流，
看最大流是否会减小，如果减小了，就是要去掉的点。记录下来最后输出就可以了。
PS:
建图也可以不加源点和汇点，直接没去掉的点，拆的两点直接连权值为1的边，有边相连的
两点连权值为INF的边。
终于理解了我写的Dinic模板一直是直接处理残余网络即e[i].val的。还有把容量网络和流量分开写的Dinic。
#include<cstdio>
#include<iostream>
#include<cstring>
#define INF 0x3f3f3f3f
#define maxn 210
#define maxm 160000
using namespace std;
struct node
{
int v,val,next;
}e[maxm<<1];
int head[maxn<<1],mp[maxn][maxn],cnt,st,en,s,t,n;
int d[maxn<<1],q[maxn<<1],mm[maxn],del[maxn];
void init()
{
memset(del,0,sizeof(del));
memset(mp,0,sizeof(mp));
st = 0;
en = 2*n+1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
scanf("%d",&mp[i][j]);
}
}
void add(int x,int y,int z)
{
e[cnt].v = y;
e[cnt].val = z;
e[cnt].next = head[x];
head[x] = cnt++;
e[cnt].v = x;
e[cnt].val = 0;
e[cnt].next = head[y];
head[y] = cnt++;
}
void build()
{
memset(head,-1,sizeof(head));
cnt = 0;
add(st,s,INF);
add(t+n,en,INF);
for(int i=1;i<=n;i++)
{
if(!del[i]) add(i,i+n,1);
for(int j=1;j<=n;j++)
{
if(mp[i][j])
add(i+n,j,INF);
}
}
add(s,s+n,INF);
add(t,t+n,INF);
}
bool bfs()
{
memset(d,-1,sizeof(d));
int f = 0,r = 0,u;
q[r++] = st;
d[st] = 0;
while(f<r)
{
u = q[f++];
for(int i=head[u];i!=-1;i=e[i].next)
{
int t = e[i].v;
if(e[i].val>0 && d[t]==-1)//>0
{
d[t] = d[u]+1;
q[r++] = t;
if(t==en) return true;
}
}
}
return false;
}
int dfs(int x,int flow)
{
if(x==en) return flow;
int ret = 0,dd;
for(int i=head[x];ret<flow && i!=-1;i=e[i].next)
{
int t = e[i].v;
if(d[t] == d[x]+1 && e[i].val)
{
dd = dfs(t,min(flow,e[i].val));
e[i].val-=dd;
e[i^1].val+=dd;
flow-=dd;
ret+=dd;
}
}
if(!ret) d[x]=-1;
return ret;
}
int Dinic()
{
int tmp = 0,maxflow = 0;
while(bfs())
{
while(tmp=dfs(st,INF))
maxflow+=tmp;
}
return maxflow;
}
void solve()
{
if(mp[s][t])
{
printf("NO ANSWER!\n");
return;
}
build();
int ans = Dinic();
printf("%d\n",ans);
if(!ans) return;
int tmp = ans,f = 0,now;
for(int i=1;i<=n;i++)
{
if(i==s || i==t) continue;
//if(!mp[s][i]) continue; //点i虽然与s不是直接连通，但可能间接连通，所以枚举时不能continue掉
del[i] = 1;
build();
now = Dinic();
if(now<tmp)
{
mm[f++] = i;
tmp = now;
}
else
del[i] = 0;
}
for(int i=0;i<f-1;i++)
printf("%d ",mm[i]);
printf("%d\n",mm[f-1]);
}
int main()
{
while(scanf("%d%d%d",&n,&s,&t)!=EOF)
{
init();
solve();
}
return 0;
}
/*
9 1 9
1 1 1 0 0 0 0 0 0
1 1 1 1 1 0 0 0 0
1 1 1 0 1 1 0 0 0
0 1 0 1 0 0 1 0 0
0 1 1 0 1 0 1 1 0
0 0 1 0 0 1 0 1 0
0 0 0 1 1 0 1 1 1
0 0 0 0 1 1 1 1 1
0 0 0 0 0 0 1 1 1
*/
poj 1815 Friendship (最小割+拆点+枚举),布布扣,bubuko.com
poj 1815 Friendship (最小割+拆点+枚举)
原文：http://blog.csdn.net/u012841845/article/details/38334493