网络流初步

不啦不啦不啦

Edmond-Karp 动能算法(EK算法)

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
int head[N], ver[M], edge[M], nex[M], incf[N], pre[N];
int n, m, s, t, tot, maxflow;
bool vis[N];

void add(int x, int y, int z) {
   ver[++tot] = y, edge[tot] = z, nex[tot] = head[x], head[x] = tot;
   ver[++tot] = x, edge[tot] = 0, nex[tot] = head[y], head[y] = tot;
}

bool bfs(){
   ms(vis, 0);
   queue<int> q;
   q.push(s); vis[s] = 1;
   incf[s] = INF; // 增广路上各边的最小剩余容量
   while(!q.empty()) {
      int x = q.front(); q.pop();
      for(int i = head[i]; i; i = nex[i]) {
         int y = ver[i];
         if(vis[y] || !edge[i]) continue; vis[y] = 1;
         incf[y] = min(incf[x], edge[i]);
         pre[y] = i; // 记录各点的前驱，便于找到最长路的方案
         q.push(y);
         if(y == t) return 1;
      }
   }
   return 0;
}
// 更新增广路及其反向边的剩余容量
void update() {
   int x = t;
   while(x != s) {
      int i = pre[x];
      edge[i] -= incf[t];
      edge[i ^ 1] += incf[t];
      x = ver[i ^ 1]; // 节点往前推
   }
   maxflow += incf[t];
}

int main() {
   while(~scanf("%d %d", &n, &m)) {
      ms(head, 0);
      s = 1, t = n, tot = 1, maxflow = 0;
      for1(i, m) {
         int x, y, z;
         scanf("%d %d %d", &x, &y, &z);
         add(x, y, z);
      }
      while(bfs()) update();
      printf("%d\n", maxflow);
   }
   return 0;
}

Dinic 算法

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
int head[N], ver[M], edge[M], nex[M], dep[N];
int n, m, s, t, tot, maxflow;

void add(int x, int y, int z) {
   ver[++tot] = y, edge[tot] = z, nex[tot] = head[x], head[x] = tot;
   ver[++tot] = x, edge[tot] = 0, nex[tot] = head[y], head[y] = tot;
}

bool bfs() {
   queue<int> q;
   ms(dep, 0); q.push(s); dep[s] = 1;
   while(!q.empty()) {
      int x = q.front(); q.pop();
      for(int i = head[x]; i; i = nex[i]) {
         int y = ver[i];
         if(dep[y] || !edge[i]) continue;
         q.push(y);
         dep[y] = dep[x] + 1;
         if(y == t) return 1;
      }
   }
   return 0;
}

int dinic(int x, int flow) {
   if(x == t) return flow;
   int rest = flow, thisflow;
   for(int i = head[x]; i && rest; i = nex[i]) {
      int y = ver[i];
      if(!edge[i] || dep[y] != dep[x] + 1) continue;
      thisflow = dinic(y, min(rest, edge[i]));
      if(!thisflow) dep[y] = 0;
      edge[i] -= thisflow;
      edge[i^1] += thisflow;
      rest -= thisflow;
   }
   return flow - rest;
}

int main() {
   scanf("%d %d", &n, &m);
   scanf("%d %d", &s, &t);
   tot = 1;
   for1(i, m) {
      int x, y, z;
      scanf("%d %d %d", &x, &y, &z);
      add(x, y, z);
   }
   int flow = 0;
   while(bfs()) while(flow = dinic(s, INF)) maxflow += flow;
   printf("%d\n", flow);
   return 0;
}

ISAP算法

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
int n, m, s, t, tot;
int head[N], ver[M], edge[M], nex[M];
int dep[N], deptot[N], cur[N], pre[N];
bool vis[N];

void add(int x, int y, int z) {
   ver[++tot] = y, edge[tot] = z, nex[tot] = head[x], head[x] = tot;
   ver[++tot] = x, edge[tot] = 0, nex[tot] = head[y], head[y] = tot;
}

bool bfs() {
   ms(vis, 0);
   queue<int> q; q.push(t);
   vis[t] = 1, dep[t] = 0;
   while(!q.empty()) {
      int x = q.front(); q.pop();
      for(int i = head[x]; i; i = nex[i]) {
         int y = ver[i], z = edge[i ^ 1];
         if(vis[y] || !z) continue;
         vis[y] = 1;
         dep[y] = dep[x] + 1;
         q.push(y);
      }
   }
   return vis[s];
}

int augement() {
   int minflow = INF;
   for(int i = pre[t]; i; i = pre[ver[i]]) {
      minflow = min(minflow, edge[i]);
   }
   for(int i = pre[t]; i; i = pre[ver[i]]) {
      edge[i] -= minflow;
      edge[i ^ 1] += minflow;
   }
}

int ISAP(int s, int t) {
   ms(deptot, 0);
   for1(i, n) cur[i] = head[i];
   int maxflow = 0, minflow = INF;
   int x = s;

   bfs();
   for1(i, n) deptot[dep[i]]++;
   
   while(dep[s] < n) {
      maxflow += augement();
      x = s;
      /* if(x == t) {
         int y = t;
         maxflow += minflow;
         for(x = pre[x]; y != s; y = x, x = pre[x]) {
            edge[cur[x]] -= minflow;
            edge[cur[x] ^ 1] += minflow;
         }
         minflow = INF;
      } */
      int flag = 0;
      for(int i = cur[x]; i; i = nex[i]) {
         int y = ver[i], z = edge[i];
         if(dep[x] != dep[y] + 1 || !z) continue;
         flag = 1;
         pre[y] = i, x = y;
         // minflow = min(minflow, z);
         // pre[y] = x, x = y; 
         break;
      }

      if(!flag) {
         int mindep = n;
         for(int i = head[x]; i; i = nex[i]) {
            int y = ver[i], z = edge[i];
            if(z && dep[y] < mindep) {
               mindep = dep[y];
               cur[x] = i;
            }
         }
         if(--deptot[dep[x]] == 0) break;
         deptot[dep[x] = mindep+1]++;
         if(x != s) x = ver[pre[x]];
      }
   }
   return maxflow;
}

void init() {
   tot = 1;
   ms(head, 0);
}

int main() {
   while(scanf("%d %d", &n, &m) != EOF) {
      init();
      for1(i, m) {
         int x, y, z;
         scanf("%d %d %d", &x, &y, &z);
         add(x, y, z);
      }
      printf("%d\n", ISAP(1, n));
   }
   return 0;
}

MCMF算法

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
int head[N], ver[M], nex[M], edge[M], cost[M];
int dis[N], incf[N], pre[N], vis[N];
int n, m, tot, s, t, maxflow, ans;

void add(int x, int y, int z, int c) {
   ver[++tot] = y, edge[tot] = z, cost[tot] = c, nex[tot] = head[x], head[x] = tot;
   ver[++tot] = x, edge[tot] = 0, cost[tot] = -c, nex[tot] = head[y], head[y] = tot;
}


bool spfa() {
   queue<int> q;
   ms(dis, _inf), ms(vis, 0);
   q.push(s); dis[s] = 0, vis[s] = 1;
   incf[s] = 1 << 30;
   while(!q.empty()) {
      int x = q.front(); q.pop(); vis[x] = 0;
      for(int i = head[x]; i; i = nex[i]) {
         if(!edge[i]) continue;
         int y = ver[i];
         if(dis[y] < dis[x] + cost[i]) {
            dis[y] = dis[x] + cost[i];
            incf[y] = min(incf[x], edge[i]);
            pre[y] = i;
            if(!vis[y]) vis[y] = 1, q.push(y);
         }
      }
   }
   if(dis[t] == _INF) return false;
   return true;
}
void update() {
   int x = t;
   while(x != s) {
      int i = pre[x];
      edge[i] -= incf[t], edge[i^1] += incf[t];
      x = ver[i ^ 1];
   }
   maxflow += incf[t];
   ans += dis[t] * incf[t];
}

int main() {
   scanf("%d %d", &n, &m, &s, &t);
   tot = 1;
   for1(i, m) {
      int x, y, z, c;
      scanf("%d %d %d %d", &x, &y, &z, &c);
      add(x, y, z, c);
   }
   while(spfa()) update();
   printf("%d\n", ans);
   return 0;
}
一只GIS专业的ACMer