城市宽带网络,由于不够用,所以需要扩大某些线路的容量,这样就可以增大网络的流量,你的任务就是寻找到这些边使得这些边容量一扩充就能增大流量。
每个城市都是源点,所以建立超级源点S,然后求S到T的最大流,从S开始dfs把点染色为1,再从T开始dfs把点染色成2,如果我们能找到一条边u,v一边是1,一边是2的话,这条边就是关键割边。注意割边不一定是关键的,因为对它扩容之后,与他临接的可能还是满流。。
#include<iostream> #include<string> #include<cstdio> #include<cstring> #include<queue> #include<vector> #include<algorithm> const int INF = 2100000000; using namespace std; //基本头文件 /* NEED-TO-DO:添加最小割方法, NEED-TO-KNOW:模板参数有两个,Vsize表示点的规模,Esize表示边的规模 (不用考虑反向边,已经*2了) HOW-TO-USE: 1.首先实例化一个对象如Net Network<110,20010> Net; //我一般都在main函数外声明好,main里面反复用 2.初始化 Net.init( N ); //N表示所需要用到的点的个数,不用考虑他们下表开始时0还是1 3.加边 Net.add( from, to, w );//添加弧,这个不用说了吧 4.求最大流 Net.MaxFlowDinic( S, T ); Net.MaxFlowSap( S, T ); //内置两种算法可以用,dinic基本可以过所有题目了,sap用来刷版OvO */ class Arc{ public: int from, to,w; Arc *next,*anti; Arc *ass(int ff, int tt,int ww,Arc* &b ){ from=ff;to = tt;w = ww;next = b;b = this;return this; } }; template< int Vsize, int Esize > class Network{ private: Arc A[ 2*Esize+10 ],*biao[ Vsize ]; int countt,d[ Vsize ],S,T,N; int bfs( void ){ queue<int> q; fill( d,d+Vsize,-1 ); d[ S ] = 0; q.push( S ); while( !q.empty() ){ int u = q.front();q.pop(); for(Arc *p=biao[u];p!=NULL;p=p->next) if( d[p->to] == -1 && p->w > 0 ) d[p->to] = d[u]+1,q.push(p->to); } return d[T] != -1; } int dinic( int u,int sum ){ int f,o; if( u == T ) return sum; o = sum; for(Arc*p=biao[u];p!=NULL&∑p=p->next) if( d[p->to] == d[u]+1 && p->w > 0 ){ f = dinic(p->to,min(p->w,sum)); p->w -= f;p->anti->w += f; sum -= f; } return o-sum; } public: Network( void ) {} Network( int n ) { init(n) ;} void init( int n ){ countt = 0;N = n; for( int i = 0; i <= n; i++ ) biao[i] = NULL; } void add( int from,int to,int w ){ Arc *p1 = A[countt++].ass( from,to,w ,biao[from]); Arc *p2 = A[countt++].ass( to,from,0,biao[ to] ); p1->anti = p2; p2->anti = p1; } int MaxFlowDinic( int s, int t ){ S = s;T = t; int total = 0; while( bfs() ) total += dinic( S,INF ); return total; } int MaxFlowSap( int s, int t){ S = s;T = t; int i,now,total,md; Arc *p,*locate,*ge[ Vsize ],*di[ Vsize ],*path[ Vsize ]; int dist[ Vsize ], cd[ Vsize ]; int his[ Vsize ], pre[ Vsize ];; bool flag; memset( dist,0, sizeof(dist) ); memset( cd, 0, sizeof(cd) ); cd[0] = N; for( i = 0; i <= N ; i++ ) di[i] = ge[i] = biao[i]; for( total = 0, now = INF,i = S; dist[i] < N; ){ his[i] = now; for( flag = false,p=di[i]; p!=NULL; p= p->next){ if( p->w > 0 && dist[i] ==dist[p->to] + 1 ){ now = min( now,p->w ); pre[ p->to ] = i; path[ p->to ] = p; di[i] = p; i = p->to; if( i == T ){ for( total += now; i != S; i = pre[i] ) path[i]->w -= now, path[i]->anti->w += now; now = INF; } flag = true; break; } } if( !flag ){ for( md = N-1,p=ge[i];p!= NULL;p=p->next ) if( p->w > 0 && dist[p->to] < md ) md = dist[p->to],locate = p; di[i] = locate; if( !(--cd[ dist[i] ] ) ) break; cd[ dist[i] = md+1 ] ++; if( i != S ) i = pre[i],now = his[i]; } } return total; } vector<int> check(int L ){ int flag[Vsize]; memset( flag,0,sizeof(flag) ); dfs1( S, flag ); dfs2( T, flag ); vector<int> v; for(int i = 0; i < 2*L; i+=2 ) if( flag[A[i].from]==1 && flag[A[i].to] ==2 ) v.push_back(i/2+1); return v; } void dfs1( int u,int *flag ){ flag[u] = 1; for( Arc*p=biao[u];p!=NULL;p=p->next ) if( !flag[p->to] && p->w ) dfs1( p->to, flag ); } void dfs2( int u, int *flag ){ flag[u]= 2; for(Arc*p=biao[u];p!=NULL;p=p->next ) if( !flag[p->to] && p->anti->w ) dfs2( p->to, flag); } }; Network< 150 , 2300 > Net; int main(void){ int N,M,L,S,T; int i,j,k,from,to,w; while( scanf("%d%d%d",&N,&M,&L) && N ){ Net.init( N+M+2 ); S = N+M+1; T = 0; for( i = 1; i <= L; i++ ){ scanf("%d%d%d",&from,&to,&w); Net.add( from,to,w ); } for( i = 1; i <=N; i++) Net.add( S, i, INF ); Net.MaxFlowSap(S,T); vector<int> v = Net.check(L); sort( v.begin(), v.end() ); for( i = 0; i < v.size(); i++ ){ if( i ) printf(" "); printf("%d",v[i]); } printf("\n"); } return 0; }