本文主要是介绍poj - 1273 - Drainage Ditches（最大流），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：M个点，N条有向路，每条沟（路）有最大排水量，问从点1到点M的最大排水量是多少(0 <= N <= 200, 2 <= M <= 200, 0 <= 每条沟的容量 <= 10000000)。
题目链接：http://poj.org/problem?id=1273
——>>LJ白书增广路算法的模板题。。。
1、不是求最小值，可以汇流的；2、测试数据有重边（开始没想到，WA了一次）。
(920K, 0MS)
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>using namespace std;const int maxn = 200 + 10;
const int INF = 0x3f3f3f3f;
int cap[maxn][maxn], a[maxn], flow[maxn][maxn], p[maxn], M;void init(){memset(cap, 0, sizeof(cap));
}int EK(int s, int t){queue<int> qu;while(!qu.empty()) qu.pop();memset(flow, 0, sizeof(flow));int f = 0;for(;;){memset(a, 0, sizeof(a));a[s] = INF;qu.push(s);while(!qu.empty()){int u = qu.front(); qu.pop();for(int v = 1; v <= M; v++) if(!a[v] && cap[u][v] > flow[u][v]){p[v] = u; qu.push(v);a[v] = min(a[u], cap[u][v] - flow[u][v]);}}if(a[t] == 0) break;for(int u = t; u != s; u = p[u]){flow[p[u]][u] += a[t];flow[u][p[u]] -= a[t];}f += a[t];}return f;
}int main()
{int N, S, E, C, i;while(scanf("%d%d", &N, &M) == 2){init();for(i = 0; i < N; i++){scanf("%d%d%d", &S, &E, &C);if(!cap[S][E]) cap[S][E] = C;else cap[S][E] += C;}printf("%d\n", EK(1, M));}return 0;
}
用Dinic算法邻接表实现，可直接解决重边问题。
(724K, 0MS)
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>using namespace std;const int maxn = 200 + 10;
const int INF = 0x3f3f3f3f;struct Edge{int u;int v;int cap;int flow;
};struct Dinic{int n, m, s, t;vector<Edge> edges;vector<int> G[maxn];bool vis[maxn];int d[maxn];int cur[maxn];void addEdge(int uu, int vv, int cap){edges.push_back((Edge){uu, vv, cap, 0});edges.push_back((Edge){vv, uu, 0, 0});m = edges.size();G[uu].push_back(m-2);G[vv].push_back(m-1);}bool bfs(){memset(vis, 0, sizeof(vis));queue<int> qu;qu.push(s);d[s] = 0;vis[s] = 1;while(!qu.empty()){int x = qu.front(); qu.pop();int si = G[x].size();for(int i = 0; i < si; i++){Edge& e = edges[G[x][i]];if(!vis[e.v] && e.cap > e.flow){vis[e.v] = 1;d[e.v] = d[x] + 1;qu.push(e.v);}}}return vis[t];}int dfs(int x, int a){if(x == t || a == 0) return a;int flow = 0, f;int si = G[x].size();for(int& i = cur[x]; i < si; i++){Edge& e = edges[G[x][i]];if(d[x] + 1 == d[e.v] && (f = dfs(e.v, min(a, e.cap-e.flow))) > 0){e.flow += f;edges[G[x][i]^1].flow -= f;flow += f;a -= f;if(a == 0) break;}}return flow;}int Maxflow(int s, int t){this->s = s;this->t = t;int flow = 0;while(bfs()){memset(cur, 0, sizeof(cur));flow += dfs(s, INF);}return flow;}
};int main()
{int N, M, S, E, C, i;while(scanf("%d%d", &N, &M) == 2){Dinic dic;for(i = 0; i < N; i++){scanf("%d%d%d", &S, &E, &C);dic.addEdge(S, E, C);}printf("%d\n", dic.Maxflow(1, M));}return 0;
}
这篇关于poj - 1273 - Drainage Ditches（最大流）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
