POJ 1273 最大流 Dinic 发表于 2019-09-02 | 分类于 ACM题解 | 阅读次数: 题目链接 思路求最大流,运用Dinic算法,先求分层图,然后用多次DFS求出增广路,把每次增广路的中的最小值相加即为最大流。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596#include <iostream>#include <algorithm>#include <string>#include <cstring>#include <queue>using namespace std;const int maxn = 10005;const int inf = 0x3f3f3f3f;typedef long long ll;int head[maxn];struct edge{ int v,w,next;} edge[10005];bool vis[10005];int tot;int deep[maxn];int bfs(int s, int t){ queue<int>Q; memset(deep, 0, sizeof(deep)); deep[s] = 1; Q.push(s); while(!Q.empty()) { int u = Q.front(); Q.pop(); for(int k = head[u]; k != -1; k = edge[k].next) { int v = edge[k].v; int w = edge[k].w; if(deep[v] == 0 && w > 0) { deep[v] = deep[u] + 1; Q.push(v); } } } if(deep[t] == 0) return 0; return 1;}void add(int u,int v, int w){ edge[tot].v = v; edge[tot].w = w; edge[tot].next = head[u]; head[u] = tot; tot++;}int t;int dfs(int s, int dis){ if(s == t) return dis; for(int k = head[s]; k != -1; k = edge[k].next) { int v = edge[k].v; int w = edge[k].w; if(deep[v] == deep[s] + 1 && w > 0) { int d = dfs(v,min(w, dis)); if(d > 0) { edge[k].w -= d; edge[k^1].w += d; return d; } } } return 0;}int main(){ int n, m,u,v,w; while(cin >> m >> n) { tot = 0; t = n; memset(head, -1, sizeof(head)); for(int i = 1; i <= m; ++i) { scanf("%d %d %d",&u,&v,&w); add(u,v,w); add(v,u,0); } ll sum = 0; while(bfs(1,n)) { while(int d = dfs(1, inf)) sum += d; } cout << sum << '\n'; }} 打赏