题目大意:用最少的花费破坏掉1和2之间的联系。
输入 n,m 以及m行 每行a,b,c 表示破坏a和b之间的联系需要花费c。
输出 破坏的边。
分析:这是一道最小割的题,其实就是最大流。不过题目要求输出割边。即一条边链接的两点分别为1可到达,和2可到达的。
#include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; int Map[55][55]; int layer[55]; int visit[55]; int n; const int oo=0x3f3f3f3f; int BFS() { queue<int>q; q.push(1); memset(layer,0,sizeof(layer)); layer[1]=1; int s; while(q.size()) { s=q.front(); q.pop(); if(s==2) return 1; for(int i=1; i<=n; i++) { if(Map[s][i]>0&&layer[i]==0) { layer[i]=layer[s]+1; q.push(i); } } } return 0; } int DFS(int s,int MaxFlow) { if(s==2) return MaxFlow; int iflow=0; for(int i=1;i<=n;i++) { if(layer[i]==layer[s]+1&&Map[s][i]) { int flow=min(MaxFlow-iflow,Map[s][i]); flow=DFS(i,flow); Map[s][i]-=flow; Map[i][s]+=flow; iflow+=flow; if(iflow==MaxFlow) break; } } if(iflow==0) layer[s]=0; return iflow; } void Dinic() { while(BFS()) { DFS(1,oo); } } int main() { int m,a,b,c; int x[550],y[550]; while(scanf("%d%d",&n,&m),m+n) { memset(Map,0,sizeof(Map)); for(int i=1; i<=m; i++) { scanf("%d%d%d",&a,&b,&c); x[i]=a; y[i]=b; Map[a][b]=Map[b][a]=c; } Dinic(); for(int i=1; i<=m; i++) { if(layer[x[i]]&&(!layer[y[i]]) || (!layer[x[i]])&&layer[y[i]])//layer【x】==0时,表示与1相连且不与2相连 printf("%d %d ",x[i],y[i]); } printf(" "); } return 0; } /* 5 8 1 4 30 1 3 70 5 3 20 4 3 5 4 5 15 5 2 10 3 2 25 2 4 50 5 8 1 4 30 1 3 70 5 3 20 4 3 5 4 5 15 5 2 10 3 2 25 2 4 50 0 0 */