本文主要是介绍hdu - 3549 - Flow Problem（最大流），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：N个点，M条边的有向图，边有权（容量），求从点1到点N的最大流（2 <= N <= 15, 0 <= M <= 1000，1 <= 每条边的容量 <= 1000）。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3549
——>>……练练……
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>using namespace std;const int maxn = 15 + 10;
const int INF = 0x3f3f3f3f;int N, M;struct Edge{int u, v, cap, flow;Edge(int u = 0, int v = 0, int cap = 0, int flow = 0):u(u), v(v), cap(cap), flow(flow){}
};struct Dinic{int m, s, t;vector<Edge> edges;vector<int> G[maxn];int d[maxn];bool vis[maxn];int cur[maxn];void init(){edges.clear();for(int i = 1; i <= N; i++) G[i].clear();}void addEdge(int u, int v, int cap){edges.push_back(Edge(u, v, cap, 0));edges.push_back(Edge(v, u, 0, 0));m = edges.size();G[u].push_back(m-2);G[v].push_back(m-1);}bool bfs(){memset(vis, 0, sizeof(vis));queue<int> qu;qu.push(s);vis[s] = 1;d[s] = 0;while(!qu.empty()){int u = qu.front(); qu.pop();int sz = G[u].size();for(int i = 0; i < sz; i++){Edge& e = edges[G[u][i]];if(!vis[e.v] && e.cap > e.flow){d[e.v] = d[u] + 1;vis[e.v] = 1;qu.push(e.v);}}}return vis[t];}int dfs(int u, int a){if(u == t || a == 0) return a;int sz = G[u].size(), f, flow = 0;for(int& i = cur[u]; i < sz; i++){Edge& e = edges[G[u][i]];if(d[e.v] == d[u] + 1 && (f = dfs(e.v, min(a, e.cap-e.flow))) > 0){cur[u] = i;e.flow += f;edges[G[u][i]^1].flow -= f;flow += f;a -= f;if(!a) 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;}
}din;void read(){int X, Y, C;scanf("%d%d", &N, &M);din.init();for(int i = 0; i < M; i++){scanf("%d%d%d", &X, &Y, &C);din.addEdge(X, Y, C);}
}int main()
{int T, kase = 1;scanf("%d", &T);while(T--){read();printf("Case %d: %d\n", kase++, din.Maxflow(1, N));}return 0;
}
这篇关于hdu - 3549 - Flow Problem（最大流）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
