题目链接：
?pid=4280
题目大意：
有N个岛屿，M条双向道路。每条路每小时最多能通过Ci个人。给你N个岛屿的坐标。问：一个小时内，
最多能将多少游客从最西边的岛送至最东边的岛屿上。
思路：
网络流求最大流的裸题。先通过坐标找到最西边的岛屿和最东边的岛屿，记录并标记为源点和汇点。然后
用链式前向星来存储图，将M条双向边加入到图中。然后用SAP算法来做，据说还没有卡SAP的网络流。
算法用了GAP优化、当前弧优化，具体参考代码。
AC代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<queue>using namespace std;const int MAXN = 100010;//最大点个数const int MAXM = MAXN*4;const int INF = 0xffffff0;struct EdgeNode{int to;int next;int w;}Edges[MAXM];int Head[MAXN],id;//链式前向星void AddEdges(int u,int v,int w){Edges[id].to = v;Edges[id].w = w;Edges[id].next = Head[u];Head[u] = id++;Edges[id].to = u;Edges[id].w = 0;Edges[id].next = Head[v];Head[v] = id++;}int Numh[MAXN],h[MAXN],curedges[MAXN],pre[MAXN];//Numh:用于GAP优化的统计高度数量数组;//h:距离标号数组;//curedges:当前弧数组//pre:前驱数组void BFS(int end,int N) //BFS求出每个点的距离标号值{memset(Numh,0,sizeof(Numh));for(int i = 1; i <= N; ++i)Numh[h[i]=N]++;h[end] = 0;Numh[N]–;Numh[0]++;queue<int> Q;Q.push(end);while(!Q.empty()){int v = Q.front();Q.pop();int i = Head[v];while(i != -1){int u = Edges[i].to;if(h[u] < N){i = Edges[i].next;continue;}h[u] = h[v] + 1;Numh[N]–;Numh[h[u]]++;Q.push(u);i = Edges[i].next;}}}int SAPMaxFlow(int start,int end,int N){int CurFlow,FlowAns = 0,temp,neck; //FlowAns:最大流，初始化为0memset(h,0,sizeof(h));memset(pre,-1,sizeof(pre));for(int i = 1; i <= N; ++i)curedges[i] = Head[i];//初始化当前弧为第一条邻接边//Numh[0] = N;BFS(end,N);int u = start;while(h[start] < N)//当h[start] >= N时，网络中肯定出现了GAP{if(u == end){CurFlow = INF;for(int i = start; i != end; i = Edges[curedges[i]].to){if(CurFlow > Edges[curedges[i]].w){neck = i;CurFlow = Edges[curedges[i]].w;}} //增广成功，寻找"瓶颈"边for(int i = start; i != end; i = Edges[curedges[i]].to){temp = curedges[i];Edges[temp].w -= CurFlow;Edges[temp^1].w += CurFlow;} //修改路径上的边容量FlowAns += CurFlow;u = neck; //下一次增广从瓶颈边开始}int i;for(i = curedges[u]; i != -1; i = Edges[i].next)if(Edges[i].w && h[u] == h[Edges[i].to]+1)break; //寻找可行弧if(i != -1)//GAP优化{curedges[u] = i;pre[Edges[i].to] = u;u = Edges[i].to;}else{if(0 == –Numh[h[u]])break;curedges[u] = Head[u];for(temp = N,i = Head[u]; i != -1; i = Edges[i].next)if(Edges[i].w)temp = min(temp,h[Edges[i].to]);h[u] = temp + 1;++Numh[h[u]];if(u != start)//重新标号并从当前点前驱重新增广u = pre[u];}}return FlowAns;}int main(){int T,N,M,u,v,w;int start,end;scanf("%d",&T);while(T–){int Max = -INF,Min = INF;scanf("%d%d",&N,&M);for(int i = 1; i <= N; ++i)//找到最西边和最东边的岛，记录源点和汇点{scanf("%d%d",&u,&v);if(u <= Min){Min = u;start = i;}if(u >= Max){Max = u;end = i;}}memset(Head,-1,sizeof(Head));id = 0;for(int i = 0; i < M; ++i)//添加边{scanf("%d%d%d",&u,&v,&w);AddEdges(u,v,w);AddEdges(v,u,w);}printf("%d\n",SAPMaxFlow(start,end,N));}return 0;}
，人生就是一场旅行，不在乎目的地，
