ZOJ 2532 Internship (寻找关键割边)

于 2011年08月15日 发布在 算法&&ACM 跳到评论

ZOJ 2532 Internship

城市宽带网络,由于不够用,所以需要扩大某些线路的容量,这样就可以增大网络的流量,你的任务就是寻找到这些边使得这些边容量一扩充就能增大流量。

每个城市都是源点,所以建立超级源点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&&sum;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;
}

留下评论!

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)