本文主要是介绍POJ1273 Drainage Ditches【最大流】【SAP】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：
http://poj.org/problem?id=1273
题目大意：
农民John的田里有M个池塘和N条水沟用来排水，池塘编号为1~M，1号池塘是所有水沟的源点，
M号池塘是水沟的汇点。给你N条水沟所连接的池塘和所能流过的水量，求整个水沟从源点到汇点
最多能流多少水。
思路：
很明显的求网络流最大流问题。用链式前向星(邻接表)来存储网络，这样就不用考虑重边问题了。这
里的重边其实就是平行边。用SAP算法+GAP优化来求最大流就可以了。SAP+GAP模板参考我的另
一篇博文：http://blog.csdn.net/lianai911/article/details/44962653
AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN = 220;
const int MAXM = MAXN*MAXN;
const int INF = 0xffffff0;struct EdgeNode
{int to;int w;int next;
}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];void BFS(int end,int N)
{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 SAP(int start,int end,int N)
{int Curflow,FlowAns = 0,temp,neck;memset(h,0,sizeof(h));memset(pre,-1,sizeof(pre));for(int i = 1; i <= N; ++i)curedges[i] = Head[i];BFS(end,N);int u = start;while(h[start] < N){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){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 N,M,u,v,w;while(~scanf("%d%d",&N,&M)){memset(Head,-1,sizeof(Head));id = 0;for(int i = 0; i < N; ++i){scanf("%d%d%d",&u,&v,&w);AddEdges(u,v,w);}printf("%d\n",SAP(1,M,M));}return 0;
}
这篇关于POJ1273 Drainage Ditches【最大流】【SAP】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
