2012天津市赛区网络赛第三题-Island Transport（hdu4280）

2012天津赛区网络赛第三题--Island Transport（hdu4280）

     题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4280

     题意：有N个岛屿之间有M双向条路，每条路每个小时最多能通过C个人，现在问一个小时内，最多能把多少个顾客从最西边的岛屿送至最东边的岛屿上。

     思路：网络流，求最大流。建图：每条路连接的两个岛屿之间建立一条容量为C的双向边，取超级源点与汇点，源点与最西边的岛屿，汇点与最东边的岛屿建立一条流量为无穷大的边。

      考点：网络流，Dinic非递归版，如果使用递归版的Dinic，将RE！

Code：

#include <stdio.h>
#include <string.h>
#define MAXN 100010
#define INF 0x3f3f3f
struct Edge{
	int u;
	int v;
	int cap;
	int next;
}edge[MAXN*2];
int head[MAXN];
int level[MAXN];
int que[MAXN];
int stack[MAXN];
int cur[MAXN];
int tot;
void addedge(int u,int v,int cap)
{
	edge[tot].u = u;
	edge[tot].v = v;
	edge[tot].cap = cap;
	edge[tot].next = head[u];
	head[u] = tot;
	tot++;

	edge[tot].u = v;
	edge[tot].v = u;
	edge[tot].cap = cap;
	edge[tot].next = head[v];
	head[v] = tot;
	tot++;
}
int BFS(int src,int des)
{
	int i;
	int front=0,real=0;
	memset(level,-1,sizeof(level));
	que[real++] = src;
	level[src] = 0;
	while(front != real)
	{
		int u = que[front++];
		front = front%MAXN;
		for(i = head[u];i != -1;i = edge[i].next)
		{
			int v = edge[i].v;
			if(edge[i].cap > 0 && level[v] == -1)
			{
				level[v] = level[u] +1;
                que[real++] = v;
				real = real%MAXN;
				if(v == des)
					return 1;
			}
		}
	}
	return 0;
}
int dinic(int src,int des)
{
	int i;
	int res = 0;
	while(BFS(src,des))
	{
		memcpy(cur,head,sizeof(head));
		int u = src;
		int top = 0;
		while(1)
		{
			if(u == des)
			{
				int min = INF,id;
				for(i=0;i<top;i++)
				{
					if(edge[stack[i]].cap < min)
					{
						min = edge[stack[i]].cap;
						id = i;
					}
				}
				for(i=0;i<top;i++)
				{
					edge[stack[i]].cap -= min;
					edge[stack[i]^1].cap += min;
				}
				res += min;
				top = id;
				u = edge[stack[top]].u;
			}
			
			for(i=cur[u];i!=-1;i = cur[u] = edge[i].next)
				if(edge[i].cap !=0 && level[u] == level[edge[i].v] -1)
					break;
            
			if(cur[u] != -1)
			{
				stack[top++] = cur[u];
				u = edge[cur[u]].v;
			}
		
			else
			{
				if(top == 0)
					break;
				level[u] = -1;
				u = edge[stack[--top]].u;
			}
		}
	}
    return res;
}
int main()
{
	int i;
	int ncase;
	scanf("%d",&ncase);
	while(ncase--)
	{
		int n,m;
		int x,y,w;
		int max = -INF,min = INF;
		int idw,ide;
		scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
		{
			scanf("%d%d",&x,&y);
			if(x>max)
			{
				max = x;
				ide = i;
			}
			if(x<min)
			{
				min = x;
				idw = i;
			}
		}
		 tot = 0;
		 memset(head,-1,sizeof(head));
         addedge(0,idw,INF);
		 addedge(ide,n+1,INF);
         for(i=1;i<=m;i++)
		 {
			 scanf("%d%d%d",&x,&y,&w);
			 addedge(x,y,w);
		 }
        int ans = dinic(0,n+1);
		printf("%d\n",ans);
	}
	return 0;
}