HDu 1532&pku 1273 Drainage Ditchesネットワークストリーム(最大ストリームEKアルゴリズム)

HDu 1532&pku 1273 Drainage Ditches(最大ストリームEKアルゴリズム)
 
本題のアルゴリズムフロー
1.初期化pre
2.BFS拡大経路Pを求める
存在しません:break,return flow;
3.P中最小値augを求める
4.P中の残存容量、フローflow+++を修正する
注意:
1°BFS拡張経路を探す
2°接頭辞配列preの遍歴
 
 

//pku1273 hdu1532

#include<stdio.h>
#include<string.h>

#define V 300
#define INF 100000000

int n, m;                                    //        n      m
int c[V][V];                                 //       

int EK( int s, int t )             //    s   t
{   
    int queue[V],pre[V],u,v,p,q,aug;
    int flow=0;
    
	while(1)
    {
		memset(pre,-1,sizeof(pre));               //          ，        
											        
		for(queue[p=q=0]=s;p<=q;p++)                     //      
        {
			u=queue[p];
			for(v=0;v<m&&pre[t]<0;v++)                  //   ？ 
				if(c[u][v]>0&&pre[v]<0)
				{
					pre[v]=u; 
					queue[++q]=v;                         //       
				}
					
			if(pre[t]>=0)                                 //        （   ） 
				break;                  //for     
        }
        if(pre[t]<0)    break;                            //        ,      
        //while    
        
        
        aug=INF;                                           //        
        for(u=pre[v=t];v!=s;v=u,u=pre[u])               //          
            if(aug>c[u][v])
				aug=c[u][v];
    	
    	
        for(u=pre[v=t];v!=s;v=u,u=pre[u])
        {
			c[u][v]-=aug;                       //    ---- 
			c[v][u]+=aug;                       //    ++++ 
		}
		flow+=aug;                             // ++++++ 
	}
	return flow;
}

int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		int x,y,cost;
		memset(c,0,sizeof(c));
		
		for(int i=0;i<n;i++)
		{	scanf("%d%d%d",&x,&y,&cost);
		    c[x-1][y-1]+=cost;
		}
		
		printf("%d
",EK(0,m-1));
	}
	return 0;
}

小さな最適化の後
 
 

//pku1273 hdu1532

#include<stdio.h>
#include<string.h>
#define V 201
#define INF 2000000000

int c[V][V],n,m;

int EK(int s,int t)
{
	int i,j,u,v,aug,flow,queue[V],p,q,pre[V];
	flow=0;
	
	while(1)
	{
		memset(pre,0,sizeof(pre));
		
		for(queue[p=q=1]=s;p<=q;p++)
		{
			u=queue[p];
			for(v=1;v<=m&&pre[t]==0;v++)
				if(c[u][v]>0&&pre[v]==0)
				{
					pre[v]=u;
					queue[++q]=v;
				}
		}
		if(pre[t]==0) break;
	
		aug=INF;
		for(v=t;v!=s;v=pre[v])
			if(aug>c[pre[v]][v]) aug=c[pre[v]][v];
		flow+=aug;
	
		for(v=t;v!=s;v=pre[v])
		{
			c[pre[v]][v]-=aug;
			//c[v][pre[v]]+=aug;        //              
		}
	}
	return flow;
}

main()
{
	int s,e,cost,i;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(c,0,sizeof(c));
		for(i=1;i<=n;i++)
		{
			scanf("%d%d%d",&s,&e,&cost);
			c[s][e]+=cost;
		}
		printf("%d
",EK(1,m));
	}
}