最大流模板

  1 /*
  2  *最大流模板（引用学长的模板。。。）
  3  * SAP（当前弧优化+GAP优化）非递归形式  7  */
  8 
  9 #include <cstring>
 10 #include <iostream>
 11 #include <cstdio>
 12 
 13 #define SETZR(a) memset(a,0,sizeof(a))
 14 
 15 using namespace std;
 16 
 17 //定义常量：边数、点数和无穷
 18 const int MAXM = 1000000;
 19 const int MAXN = 10000;
 20 const int INF = 1000000000;
 21 
 22 //边的结构体
 23 //此模板中图以池子法存储
 24 
 25 struct record {
 26     int v, f, next;
 27 } edge[MAXM];
 28 
 29 /*
 30  * 变量说明：
 31  * pointer为各点出度头指针
 32  * dis为距离标号
 33  * vh记录每个距离标号点的数量，用于GAP优化
 34  * his记录各点入栈时的流量，用于退栈
 35  * di记录各点当前弧
 36  * pre记录各点前驱结点，同样用于退栈
 37  */
 38 int n, m, s, t, cas, cl;
 39 int pointer[MAXN], dis[MAXN], vh[MAXN];
 40 int his[MAXN], di[MAXN], pre[MAXN];
 41 
 42 void connect(int a, int b, int f) {
 43     cl++;
 44     edge[cl].next = pointer[a];
 45     edge[cl].v = b;
 46     edge[cl].f = f;
 47     pointer[a] = cl;
 48     cl++;
 49     edge[cl].next = pointer[b];
 50     edge[cl].v = a;
 51     edge[cl].f = 0; //若为无向边，则f = f
 52     pointer[b] = cl;
 53 }
 54 
 55 int main() {
 56     scanf("%d", &cas);
 57     while (cas--) {
 58         scanf("%d%d%d%d", &n, &m, &s, &t);
 59         //初始化
 60         cl = 1;
 61         SETZR(dis);
 62         SETZR(vh);
 63         SETZR(pointer);
 64         //建图
 65         for (int i = 0; i < m; i++) {
 66             int p, k, w;
 67             scanf("%d%d%d", &p, &k, &w);
 68             connect(p, k, w);
 69         }
 70         //最大流过程
 71         vh[0] = n; //初始化GAP数组（默认所有点的距离标号均为0，则距离标号为0的点数量为n）
 72         for (int i = 0; i < n; i++) di[i] = pointer[i]; //初始化当前弧
 73         int i = s, aug = INF, flow = 0; //初始化一些变量，flow为全局流量，aug为当前增广路的流量
 74         bool flag = 0; //标记变量，记录是否找到了一条增广路（若没有找到则修正距离标号）
 75         while (dis[s] < n) {
 76             his[i] = aug; //保存当前流量
 77             flag = 0;
 78             int p = di[i];
 79             while (p != 0) {
 80                 if ((edge[p].f > 0) && (dis[edge[p].v] + 1 == dis[i])) {//利用距离标号判定可行弧
 81                     flag = 1; //发现可行弧
 82                     di[i] = p; //更新当前弧
 83                     aug = min(aug, edge[p].f); //更新当前流量
 84                     pre[edge[p].v] = p; //记录前驱结点
 85                     i = edge[p].v; //在弧上向前滑动
 86                     if (i == t) {//遇到汇点，发现可增广路
 87                         flow += aug; //更新全局流量
 88                         while (i != s) {//减少增广路上相应弧的容量，并增加其反向边容量
 89                             edge[pre[i]].f -= aug;
 90                             edge[pre[i]^1].f += aug;
 91                             i = edge[pre[i]^1].v;
 92                         }
 93                         aug = INF;
 94                     }
 95                     break;
 96                 }
 97                 p = edge[p].next;
 98             }
 99             if (flag) continue; //若发现可行弧则继续，否则更新标号
100             int min = n - 1;
101             p = pointer[i];
102             while (p != 0) {
103                 if ((edge[p].f > 0) && (dis[edge[p].v] < min)) {
104                     di[i] = p; //不要忘了重置当前弧
105                     min = dis[edge[p].v];
106                 }
107                 p = edge[p].next;
108             }
109             --vh[dis[i]];
110             if (vh[dis[i]] == 0) break; //更新vh数组，若发现距离断层，则算法结束（GAP优化）
111             dis[i] = min + 1;
112             ++vh[dis[i]];
113             if (i != s) {//退栈过程
114                 i = edge[pre[i]^1].v;
115                 aug = his[i];
116             }
117         }
118         //输出答案
119         printf("%d\n", flow);
120     }
121     return 0;
122 }