POJ 1815 Friendship 网络流 Dinic
POJ 1815 Friendship
Dinic，拆点建图，割
传送门：POJ
题意
N个人，S源点，T汇点。然后给你个邻接矩阵，a[i][j]为1表示i和j能联系到彼此。等于0表示彼此不认识。
问你至少删除几个人，让s不能通过中间人联系到t。不能删除s或t。
思路
问的是删除哪个人，而非删除哪条边，但是割集是边集，所以拆点建图。k点，拆成k和k+n，k表示k入，k+n表示k出。对于源点s、汇点t，建s到s+n，t到t+n的边，容量是无穷；对于其他点k，建k到k+n的边，容量是1；对于原图的a到b边，建a+n到b的容量无穷大的边。这样成为割的只可能是容量为1的边，就是表示删除点k。
然后跑一遍dinic，跑完之后按序号枚举点，重新构图，删去该点。重新跑Dinic，如果新流比原流小，那么记录这个点，把删除该点的图作为新图，总流减一，在去删下一个点；如果新流等于原流，那么吧图还原，在删下一个。到流等于0停止。
我的做法是删点，如果新流小，那么记录点，还原图；如果新流不变，那么还原图。不知道为什么不对。
代码
ac的
//Dinic
#include void AddEdge(int from,int to,int cap)
{edges.push_back(Edge(from,to,cap,0));edges.push_back(Edge(to,from,0,0));//单向边第三个参数写0，双向边写capm=edges.size();G[from].push_back(m-2);G[to].push_back(m-1);
}bool BFS(int s,int t)
{memset(vis,0,sizeof(vis));queue<int> Q;Q.push(s);d[s]=0;vis[s]=1;while(!Q.empty()){int x=Q.front();Q.pop();for(int i=0;iif(!vis[e.to]&&e.cap>e.flow)//残量网络{vis[e.to]=1;d[e.to]=d[x]+1;Q.push(e.to);}}}return vis[t];
}
int DFS(int x,int a,int s,int t)
{if(x==t||a==0) return a;int flow=0,f;for(int& i=cur[x];iif(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow),s,t))>0){e.flow+=f;edges[G[x][i]^1].flow-=f;flow+=f;a-=f;if(a==0) break;}}return flow;
}
int Maxflow(int s,int t)
{int flow=0;while(BFS(s,t)){memset(cur,0,sizeof(cur));flow+=DFS(s,oo,s,t);}return flow;
}
int build(int n,int s,int t)
{edges.clear();for(int i=0;ifor(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(i!=j){if(mp[i][j]==1)AddEdge(i+n,j,oo);}else if(i==s||i==t){AddEdge(j,i+n,oo);}else{AddEdge(i,i+n,1);}}return Maxflow(s,t+n);
}
int main()
{//freopen("in.txt","r",stdin);int n,s,t;scanf("%d%d%d",&n,&s,&t);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&mp[i][j]);if(mp[s][t]==1){printf("NO ANSWER!\n");}else{vector<int> rr;rr.clear();int res=build(n,s,t);if(res==0) printf("0\n");else{printf("%d\n",res);for(int i=1;i<=n;i++){if(i==s||i==t) continue;for(int j=1;j<=n;j++)for(int k=1;k<=n;k++){g[j][k]=mp[j][k];if(j==i||k==i)mp[j][k]=0;}int tres=build(n,s,t);if(treselsefor(int j=1;j<=n;j++) //最大流不变则恢复原图for(int k=1;k<=n;k++)mp[j][k]=g[j][k];if(res==0) break;}}for(int i=0;iprintf("%d%c",rr[i],i==rr.size()-1 ? '\n' : ' ');}}return 0;
} 我的
//Dinic
#include void AddEdge(int from,int to,int cap)
{edges.push_back(Edge(from,to,cap,0));edges.push_back(Edge(to,from,0,0));//单向边第三个参数写0，双向边写capm=edges.size();G[from].push_back(m-2);G[to].push_back(m-1);
}bool BFS(int s,int t)
{memset(vis,0,sizeof(vis));queue<int> Q;Q.push(s);d[s]=0;vis[s]=1;while(!Q.empty()){int x=Q.front();Q.pop();for(int i=0;iif(!vis[e.to]&&e.cap>e.flow)//残量网络{vis[e.to]=1;d[e.to]=d[x]+1;Q.push(e.to);}}}return vis[t];
}
int DFS(int x,int a,int s,int t)
{if(x==t||a==0) return a;int flow=0,f;for(int& i=cur[x];iif(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow),s,t))>0){e.flow+=f;edges[G[x][i]^1].flow-=f;flow+=f;a-=f;if(a==0) break;}}return flow;
}
int Maxflow(int s,int t)
{int flow=0;while(BFS(s,t)){memset(cur,0,sizeof(cur));flow+=DFS(s,oo,s,t);}return flow;
}
int build(int n,int s,int t,int ignor)
{edges.clear();for(int i=0;ifor(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(i==ignor||j==ignor) continue;if(i!=j){if(mp[i][j]==1)AddEdge(i+n,j,oo);}else if(i==s||i==t){AddEdge(j,i+n,oo);}else{AddEdge(i,i+n,1);}}return Maxflow(s,t+n);
}
int main()
{//freopen("in.txt","r",stdin);//freopen("outb.txt","w",stdout);int n,s,t;while(~scanf("%d%d%d",&n,&s,&t)){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&mp[i][j]);if(mp[s][t]==1){printf("NO ANSWER!\n");}else{vector<int> rr;rr.clear();int res=build(n,s,t,0);if(res==0) printf("0\n");else{printf("%d\n",res);for(int i=1;i<=n;i++){if(i==s||i==t) continue;int tres=build(n,s,t,i);if(tres!=res){rr.push_back(i);}if(rr.size()==res) break;}}for(int i=0;iprintf("%d%c",rr[i],i==rr.size()-1 ? '\n' : ' ');}}}return 0;
} 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！