本文共 1474 字，大约阅读时间需要 4 分钟。
n条边，m个节点。
求最大流。
多组输入。
增广路算法。
#include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const int MAXN = 200 + 10;const int INF = 1e9 + 10;struct Edge{ int _from, _to, _cap, _flow; Edge(int f, int t, int c, int l):_from(f), _to(t), _cap(c), _flow(l) {};};vector G[MAXN];vector edges;int a[MAXN], p[MAXN];int n, m;int Get_Flow(){ LL flow = 0; while (1) { memset(a, 0, sizeof(a)); queue que; que.push(1); a[1] = INF; while (!que.empty()) { int x = que.front(); que.pop(); for (int i = 0;i < G[x].size();i++) { Edge & e = edges[G[x][i]]; if (!a[e._to] && e._cap > e._flow) { p[e._to] = G[x][i]; a[e._to] = min(a[x], e._cap - e._flow); que.push(e._to); } } if (a[m]) break; } if (a[m] == 0) break; for (int u = m;u != 1;u = edges[p[u]]._from) { edges[p[u]]._flow += a[m]; edges[p[u] ^ 1]._flow -= a[m]; } flow += a[m]; } return flow;}void Init(){ edges.clear(); for (int i = 1;i <= m;i++) G[i].clear();}int main(){ int l, r, c; while(~scanf("%d%d", &n, &m)) { Init(); for (int i = 1; i <= n; i++) { scanf("%d%d%d", &l, &r, &c); edges.emplace_back(l, r, c, 0); edges.emplace_back(r, l, 0, 0); int sum = edges.size(); G[l].push_back(sum - 2); G[r].push_back(sum - 1); } printf("%d\n", Get_Flow()); } return 0;}
转载于:https://www.cnblogs.com/YDDDD/p/10545003.html