题目见SYZOJ
网络流初步。
恩，经历千辛万苦，重构代码无数遍之后，终于把第一发dinic完成了。现在的手速，再写dinic只用7分钟。。。。。
|
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 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
#include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <cstdlib> #include <cstring> using namespace std; const int MX = 305; const int INF = 100000007; int dis[MX], head[MX]; int tot, s, t, m, n; class edge { public: int fr, to, le, ne; }e[MX * MX]; void addedge(int a, int b, int v) {//邻接表加边，不解释了 tot++; e[tot].fr = a; e[tot].to = b; e[tot].le = v; e[tot].ne = head[a]; head[a] = tot; tot++;//添加反向边 e[tot].fr = b; e[tot].to = a; e[tot].ne = head[b]; head[b] = tot; } bool bfs() {//每次进行广搜搜查找，对残量网络进行分层。 queue <int> q; int now, to; memset(dis, 0, sizeof(dis)); dis[s] = 1; q.push(s); while (!q.empty()) { now = q.front(); q.pop(); for (int i = head[now]; i; i = e[i].ne) { to = e[i].to; if (((!dis[to]) || dis[to] == dis[now] + 1) && e[i].le) { dis[to] = dis[now] + 1; q.push(to); } } } return dis[t]; } int dfs(int now, int min_flow) {//深搜查找最大流 int to, now_flow; if (now == t) { return min_flow; } for (int i = head[now]; i; i = e[i].ne) { to = e[i].to; if (dis[to] != dis[now] + 1) continue;//优化，如果下一条边不是下一层，直接跳过 if (e[i].le <= 0) continue;//如果这一条边已经没有余量，跳过 now_flow = dfs(to, min(min_flow, e[i].le)); if (!now_flow) continue; e[i].le -= now_flow; if (i % 2) e[i + 1].le += now_flow;//反向边处理 else e[i - 1].le += now_flow; return now_flow; } return 0; } int dinic() { int ans = 0; int tmp; while (bfs()) { //cout << "flag\n"; while (tmp = dfs(s, INF)) ans += tmp; } return ans; } int main() { int a, b, v; scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d%d%d", &a, &b, &v); addedge(a, b, v); } s = 1; t = m; printf("%d\n", dinic()); return 0; } |