参考链接：https://www.cnblogs.com/widerg/p/9387909.html
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | #include<iostream> #include<algorithm> #include<queue> #include<cstring> using namespace std; const int eN = 100005; const int vN = 10005; const int INF = 0x7f7f7f7f; int n, m, s, t; int ePtr = -1; //e的实际存储只能从偶数号顶点开始，奇数号顶点存储反向边 int to[eN<<1], nxt[eN<<1], value[eN<<1]; int head[vN], dis[vN]; inline void createEdge(int u, int v, int w) { to[++ePtr] = v; value[ePtr] = w; nxt[ePtr] = head[u]; head[u] = ePtr; } bool bfs(int s, int t) { queue<int> q; memset(dis, 0x7f, sizeof(dis)); dis[s] = 0; q.push(s); while (!q.empty()) { int x = q.front(); q.pop(); for (int i = head[x]; ~i; i = nxt[i]) { int dest = to[i]; if (dis[dest] == INF && value[i] != 0) { dis[dest] = dis[x] + 1; q.push(dest); } } } return dis[t] != INF; } int dfs(int x, int t, int maxflow) { if (x == t)return maxflow; int ans = 0; for (int i = head[x]; ~i; i = nxt[i]) { int dest = to[i]; if (dis[dest] != dis[x] + 1 || value[i] == 0 || ans >= maxflow)continue; int f = dfs(dest, t, min(value[i], maxflow - ans)); value[i] -= f; value[i ^ 1] += f; ans += f; } return ans; } int dinic(int s, int t) { int ans = 0; while (bfs(s, t))ans += dfs(s, t, INF); return ans; } int main() { memset(head, -1, sizeof(head)); scanf("%d%d%d%d", &n, &m, &s, &t); for (int i = 1; i <= m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); createEdge(u, v, w); createEdge(v, u, 0);//第0号边被占用，这条语句为下一个边留下空间 } printf("%d", dinic(s, t)); } |