HDU1532 Drainage Ditches（最大流）

學了一下午網絡流，AC了這道模闆題

勉強算是自己敲的，debug時參照了下模闆，模闆參照kuangbin大神

鄰接表+isap算法

#include <stdio.h>
#include <string.h>
#define MAXN 210
#define MAXM 420
#define INF 0x3f3f3f3f

struct node{
	int to,next,cap;
}edge[MAXM];

int cnt,head[MAXN];
int dis[MAXN],gap[MAXN],cur[MAXN],path[MAXN],queue[MAXN];

void addedge(int u,int v,int w)
{
	edge[cnt].to=v;
	edge[cnt].cap=w;
	edge[cnt].next=head[u];
	head[u]=cnt++;
	edge[cnt].to=u;
	edge[cnt].cap=0;
	edge[cnt].next=head[v];
	head[v]=cnt++;
}

void bfs(int start,int end)
{
	memset(dis,-1,sizeof(dis));
	memset(gap,0,sizeof(gap));
	int front,rear;
	front=rear=0;
	queue[rear++]=end;
	dis[end]=0;
	gap[0]=1;
	while(front<rear)
	{
		int i,v,u=queue[front];
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			v=edge[i].to;
			if(dis[v]!=-1)
				continue;
			queue[rear++]=v;
			dis[v]=dis[u]+1;
			gap[dis[v]]++;
		}
		front++;
	}
}

int sap(int start,int end,int N)
{
	bfs(start,end);
	memcpy(cur,head,sizeof(head));
	int top=0;
	int u=start;
	int ans=0;
	while(dis[start]<N)
	{
		if(u==end)
		{
			int i,inser,min=INF;
			for(i=0;i<top;i++)
				if(min>edge[path[i]].cap)
				{
					min=edge[path[i]].cap;
					inser=i;
				}
			for(i=0;i<top;i++)
			{
				edge[path[i]].cap-=min;
				edge[path[i]^1].cap+=min;
			}
			ans+=min;
			top=inser;
			u=edge[path[top]^1].to;
			continue;
		}
		int i,v,flag=0;
		for(i=cur[u];i!=-1;i=edge[i].next)
		{
			v=edge[i].to;
			if(edge[i].cap&&dis[v]+1==dis[u])
			{
				flag=1;
				cur[u]=path[top++]=i;
				u=v;
				break;
			}
		}
		if(flag)
			continue;
		int min=N;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			v=edge[i].to;
			if(edge[i].cap&&dis[v]<min)
			{
				min=dis[v];
				cur[u]=i;
			}
		}
		gap[dis[u]]--;
		if(!gap[dis[u]])
			return ans;
		dis[u]=min+1;
		gap[dis[u]]++;
		if(start!=u)
			u=edge[path[--top]^1].to;
	}
	return ans;
}

int main()
{
	int N,M,u,v,w;
	while(scanf("%d%d",&N,&M)!=EOF)
	{
		cnt=0;
		memset(head,-1,sizeof(head));
		while(N--)
		{
			scanf("%d%d%d",&u,&v,&w);
			addedge(u,v,w);
		}
		printf("%d\n",sap(1,M,M));
	}
	return 0;
}