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 0x3f3f3fstruct 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;}