本文主要是介绍HDU4280 Island Transport【最大流】【SAP】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：
http://acm.hdu.edu.cn/showproblem.php?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;
}
这篇关于HDU4280 Island Transport【最大流】【SAP】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
