HDU3549 最大流入门

发表于 分类于

第一次写 EK，写了一个晚上没有什么大的进展，仔仔细细研究了一下论文，自己想了 BFS 找增广路的过程，写了一个邻接矩阵版的 EK 交上去，居然只跑了 30 多毫秒，不知道什么情况。。。。

我的代码：

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 <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>

using namespace std;

const int oo = 0x3f3f3f3f;

int get() {
  char ch;
  int flag = 0, tmp = 0;
  for (ch = getchar(); ch < 48 || ch > 57; ch = getchar())
    if (ch == int('-')) break;
  if (ch == int('-'))
    flag = 1;
  else
    tmp = int(ch) - 48;
  for (ch = getchar(); 48 <= ch && ch <= 57; ch = getchar())
    tmp = tmp * 10 + int(ch) - 48;
  return (flag) ? -tmp : tmp;
}

int c[20][20], pre[20], low[20];
int st, ed, n;

int bfs() {
  bool vis[20] = {0};
  memset(low, 0, sizeof(low));
  queue<int> q;
  low[st] = oo;
  q.push(st);
  vis[st] = true;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v = 1; v <= n; v++) {
      if (!vis[v] && c[u][v]) {
        vis[v] = true;
        pre[v] = u;
        q.push(v);
        low[v] = min(c[u][v], low[u]);
      }
    }
  }
  if (low[st]) {
    int u = ed;
    do {
      c[pre[u]][u] -= low[ed];
      c[u][pre[u]] += low[ed];
      u = pre[u];
    } while (u != st);
  }
  return low[ed];
}

int maxflow() {
  int ret = 0;
  do {
    ret += bfs();
  } while (low[ed]);
  return ret;
}

int main() {
  int t, m;
  int cnt = 0;
  t = get();
  while (t--) {
    cnt++;
    n = get();
    m = get();
    memset(c, 0, sizeof(c));
    for (int i = 0; i < m; i++) {
      int u = get();
      int v = get();
      int w = get();
      c[u][v] += w;
    }
    st = 1;
    ed = n;
    printf("Case %d: %d\n", cnt, maxflow());
  }
  return 0;
}

注意 BFS 过程，low 作为全局变量。。。