poj 1815 Friendship 网络流
求最小割就没什么可说的了。关键是怎么判断一条边能不能成为割边，如果能够成为割边，那么做完最大流之后，起点肯定不能达到终点，否则这条边容量减小对最大流没有影响。那么怎么去掉这条边呢？反向压一次流。
#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn=4e2+9,inf=1e7;int n,s,t;int d[maxn][maxn],que[maxn],level[maxn];int use[maxn],visit[maxn],ff[maxn];bool makelevel(int s,int t){ memset(level,0,sizeof(level)); int front=1,end=0; que[++end]=s; level[s]=1; while(front<=end) { int u=que[front++]; if(u==t) return true; for(int v=1;v<=n+n;v++) if(d[u][v]&&!level[v]) { level[v]=level[u]+1; que[++end]=v; } } return false;}int dfs(int now,int t,int maxf){ if(now==t) return maxf; int ret=0; for(int u=1;u<=n+n;u++) if(d[now][u]&&level[u]==level[now]+1) { int f=dfs(u,t,min(maxf-ret,d[now][u])); d[now][u]-=f; d[u][now]+=f; ret+=f; if(ret==maxf) return ret; } return ret;}int maxflow(int s,int t){ int ans=0; while(makelevel(s,t)) { ans+=dfs(s,t,inf); } return ans;}bool dfs(int now,int t){ visit[now]=1; if(now==t) return true; for(int u=1;u<=n+n;u++) if(d[now][u]&&!visit[u]) { if(dfs(u,t)) return true; } return false;}void prin(){ for(int i=1;i<=n;i++) { printf("%d ",d[i*2][i*2-1]); } cout<<endl;}int dfs1(int now,int t,int maxf){ ff[now]=1; if(now==t) return maxf; int ret=0; for(int u=1;u<=n+n;u++) if(d[now][u]&&!ff[u]) { int f=dfs1(u,t,min(maxf-ret,d[now][u])); d[now][u]-=f; d[u][now]+=f; ret+=f; if(ret==maxf) return ret; } return ret;}int main(){// freopen("in.txt","r",stdin); while(scanf("%d%d%d",&n,&s,&t)!=EOF) { memset(d,0,sizeof(d)); bool flag=false; for(int i=1,tmp;i<=n;i++) for(int j=1;j<=n;j++) { scanf("%d",&d[i*2][j*2-1]); if(d[i*2][j*2-1]) d[i*2][j*2-1]=inf; } if(d[s*2][t*2-1]) { printf("NO ANSWER!\n"); continue; } for(int i=1;i<=n;i++) d[i*2-1][i*2]=1,d[i*2][i*2-1]=0; int ans=maxflow(s*2,t*2-1); cout<<ans<<endl; memset(use,0,sizeof(use)); for(int i=1;i<=n;i++) { memset(visit,0,sizeof(visit)); if(!dfs(i*2-1,i*2)) {// prin(); use[i]=1; memset(ff,0,sizeof(ff)); dfs1(t*2-1,i*2,1); memset(ff,0,sizeof(ff)); dfs1(i*2-1,s*2,1); d[i*2][i*2-1]=0;// prin(); } } for(int i=1,flag=0;i<=n;i++) if(use[i]&&flag) printf(" %d",i); else if(use[i]) { printf("%d",i); flag=1; } cout<<endl; } return 0;}