- 1 int SPFA()
- 2 {
- 3 int head, tail, i, node, p;
- 4 for
- (i =
- 1
- ; i <= ver; ++
- i) {
- 5
- dis[i] =
- INF;
- 6
- path[i] =
- 0;
- 7
- bok[i] =
- false;
- 8 }
- 9
- dis[s] =
- 0;
- 10
- head = tail =
- 1;
- 11
- que[tail++] =
- s;
- 12
- bok[s] =
- true;
- 13 while
- (head <
- tail) {
- 14
- node = que[head++
- ];
- 15
- bok[node] =
- false;
- 16 for
- (p = fst[node]; p; p =
- nxt[p]) {
- 17 if
- (c[p] <=
- 0
- || dis[node] + w[p] >=
- dis[v[p]])
- 18 continue;
- 19
- dis[v[p]] = dis[node] +
- w[p];
- 20
- path[v[p]] =
- p
- 21 if (bok[v[p]])
- 22 continue;
- 23
- que[tail++] =
- v[p];
- 24
- bok[v[p]] =
- true;
- 25 }
- 26 }
- 27 return dis[t];
- 28 }
- 29 void modify()
- 30 {
- 31 int
- tmp =
- INF;
- 32 for
- (p = path[t]; p; p =
- path[u[p]])
- 33
- tmp =
- min(c[p], tmp);
- 34
- cost += tmp *
- dis[t];
- 35
- maxflow +=
- tmp;
- 36 for
- (p = path[t]; p; p =
- path[u[p]]) {
- 37
- c[p] -=
- tmp;
- 38
- c[p +
- 1
- ] +=
- tmp;
- 39 }
- 40 return ;
- 41 }
- 42
- 43 int main()
- 44 {
- 45 /* input */
- 46 while
- (SPFA() <
- INF)
- 47 modify();
- 48 /* now we get 'cost' and 'maxflow' */
- 49 return 0;
- 50
- }
来源: http://www.bubuko.com/infodetail-2163577.html