最大ストリーム(Dinic模式)——HDOJ 1532

HDOJ 1532 Drainage Ditch
このテーマはDinicアルゴリズムの模版テーマで、前のブログです. 最大ストリーム——HDOJ 3549 EKアルゴリズムとして使用されるテンプレートテーマです.
Dinicアルゴリズムについての説明はネット上にたくさんあります.ここでは多くの話をしません.わかりやすいように紹介します. http://comzyh.tk/blog/archives/568/#Dinic-コード

/*
HDOJ 1532
             Dinic  ，     ，    
*/

#include <iostream>
using namespace std;

#define min(a,b) (a)<(b)?a:b
#define MAX 0x5fffffff

int map[250][250];	//     
int dis[250];	//     ,    
int que[2000],front,rear;	//BFS   , ,  
int N,M,ANS;	//N:  ;M,  

int BFS()
{
	int i,j;
	memset(dis,0xff,sizeof(dis));// -1   
	dis[1]=0;
	front=rear=0;
	que[0]=1;
	while (front <= rear)
	{
		j=que[front++];
		for (i=1;i<=N;i++)
			if (dis[i]<0 && map[j][i]>0)
			{
				dis[i]=dis[j]+1; 
				que[++rear]=i;
			}
	}
	if (dis[N]>0)
        return 1;
	else
        return 0;//   DIS   ,  BFS     
}

//Find      ,           ,  0       
int find(int x,int low)//Low         (      )       
{
    int i,a=0;
    if (x==N)
		return low;//    
    for(i=1;i<=N;i++)
		if (map[x][i] >0 //   
			&& dis[i]==dis[x]+1 //         
			&&(a=find(i,min(low,map[x][i]))))//    (a <> 0) 
		{
			map[x][i] -= a;
			map[i][x] += a;
			return a;
		}
		return 0;
		
}

int main()
{
    int i,j,f,t,flow,tans;
    while (scanf("%d%d",&M,&N)!=EOF)
	{
		memset(map,0,sizeof(map));
		for(i=1;i<=M;i++)
		{
			scanf("%d%d%d",&f,&t,&flow);
			map[f][t] += flow;
		}		
		ANS=0;
		while(BFS())//         ,  BFS        
		{
			while(tans=find(1,0x7fffffff))
				ANS+=tans;//  BFS        ,        
		}
		printf("%d
",ANS);
    }
    return 0;
}