HDU 1532 Drainage Ditches Dinicアルゴリズム

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1532
 
テーマ:
      大雨が降った时、ジョンの农场は雨に浸かって、仕方なくジョンは水沟を建设しなければならなくて、しかもネットの水沟で、しかも聡明なジョンはまた水の流速をコントロールして、本題はあなたに最大の流速を求めさせて、间违いなく最大の流れを求めることに运用します.題中Nは溝数,Mは溝の頂点であり,次いでSi,Ei,Ciはそれぞれ溝の起点,終点およびその容量である.ソースポイント1から終点Mまでの最大流速を求める.重辺に注意
 
http://blog.csdn.net/no_retreats/article/details/7883619 この中で私は一般的な拡張アルゴリズムを使って書く効率が高くなくて、いくつかのデータの大量の穴のお父さんのテーマに対して断固としてタイムアウトして、今回もこの問題で私のDinicアルゴリズムを強固にして、このアルゴリズムの効率はとても高くて、複雑度O(m*n^2)
 
Dinicアルゴリズムの実装には、次の手順があります.
1:容量ネットワークおよびネットワーク・フローの初期化
2:残留ネットワークと階層ネットワークを構築し、ポイントが階層ネットワークにない場合、アルゴリズムは出力最大ストリームを終了する
3:階層ネットワークにおいて一度のDFSで拡張を行い、DFSの実行が完了すると、その段階の拡張も完了する.
4:手順2に進む
参照コード:

#include<iostream>
using namespace std;
#include<cstdio>
#include<queue>
#define INF 0x7fffffff
#define min(a,b) a<b?a:b
int N,M;
int level[205];
int Si,Ei,Ci;
struct Dinic
{
	int c;
	int f;
}edge[205][205];
bool dinic_bfs()//      
{
	queue<int> Q;
	memset(level,0,sizeof(level));//          0
	Q.push(1);
	level[1]=1;
	int u,v;
	while(!Q.empty())
	{
		u=Q.front();
		Q.pop();
		for(v=1;v<=M;v++)
		{
			if(!level[v]&&edge[u][v].c>edge[u][v].f)//        ，  u，v,   
			{
				level[v]=level[u]+1;//       
				Q.push(v);
			}
		}
	}
	return level[M]!=0;//   false            
}
int dinic_dfs(int u,int cp)//    
{
	int tmp=cp;
	int v,t;
	if(u==M)
		return cp;
	for(v=1;v<=M&&tmp;v++)
	{
		if(level[u]+1==level[v])
		{
			if(edge[u][v].c>edge[u][v].f)
			{
				t=dinic_dfs(v,min(tmp,edge[u][v].c-edge[u][v].f));
				edge[u][v].f+=t;
				edge[v][u].f-=t;
				tmp-=t;
			}
		}
	}
	return cp-tmp;
}
int dinic()//     
{
	int sum,tf;
	sum=tf=0;
	while(dinic_bfs())
	{
		while(tf=dinic_dfs(1,INF))
		{
			sum+=tf;
		}
	}
	return sum;
}
int main()
{
	while(~scanf("%d%d",&N,&M))
	{
		memset(edge,0,sizeof(edge));
		while(N--)
		{
			scanf("%d%d%d",&Si,&Ei,&Ci);
			edge[Si][Ei].c+=Ci;//    
		}
		int S=dinic();
		printf("%d
",S);
	}
	return 0;
}