[关闭]
@WangYixu 2018-06-21T05:20:47.000000Z 字数 5176 阅读 1164

OI 笔记 算法 网络流

网络流

24题

最大流

Edmonds-Karp

EK算法基于一种贪心的思想，每次在图中寻找“增广路”（不是二分图里的那个）。

首先要对网络流重新构建，计算每条边容量与流量之差，简称残量，构成残量网络。

如图就是一个残量网络。

残量网络中的从源点到汇点的有向路径称为增广路，对于增广路，将其中的每个弧都增大最小残量的流量，那么，流量会增大并且不会违法。图中红边即为一条增广路。
这个操作称为增广。

找增广路时应该使用bfs。

无法增广时获得最大流。

代码：

  1. struct Edge {
  2.     int from, to, cap, flow;
  3.     /*起点*终点*容量*流量*/
  4.     Edge(int f = 0, int t = 0, int c = 0, int fl = 0) : from(f), to(t), cap(c), flow(fl) {}
  5. };
  7. int n, m;
  8. int head[N], next[M], cnt = 1;  //邻接表
  9. Edge e[M];                      //邻接表
  10. int p[N];                       //入弧 
  11. int a[N];                       //入弧的可改进量 
  12. int q[Q], hd, tl;               //bfs队列
  14. //加边，正反两条边，正边是原弧，反边是反流量弧
  15. //cnt从1开始,有边p^1为反边
  16. inline void adde(int from, int to, int cap) {
  17.     ++cnt;
  18.     e[cnt] = Edge(from, to, cap, 0);
  19.     next[cnt] = head[from];
  20.     head[from] = cnt;
  21.     ++cnt;
  22.     e[cnt] = Edge(to, from, 0, 0);
  23.     next[cnt] = head[to];
  24.     head[to] = cnt;
  25. }
  27. inline int EK(int s, int t) {
  28.     int flow = 0;                                                   //初始化流量
  29.     int tmp;                                                
  30.     while (1) {                                                     //增广
  31.         memset(a, 0, sizeof(a));                                    //初始化改进量
  32.         hd = tl = 0;                                                //初始化队列
  33.         q[tl++ % Q] = s;                                            //源点入队
  34.         a[s] = INF;                                                 //设为INF，一是标记访问过，二是防止干扰
  35.         while (hd != tl) {                                          //bfs
  36.             tmp = q[hd++ % Q];
  37.             for(int i = head[tmp]; i; i = next[i]) {
  38.                 if(!a[e[i].to] && e[i].cap > e[i].flow) {           //没访问过（防止在环上不断绕圈）且还有残量
  39.                     p[e[i].to] = i;                                 //记录入弧和计算可改进量           
  40.                     a[e[i].to] = min(a[tmp], e[i].cap - e[i].flow);
  41.                     q[tl++ % Q] = e[i].to;
  42.                 }
  43.             }
  44.             if(a[t]) break;                                         //找到增广路，退出bfs
  45.         }
  46.         if(!a[t]) break;                                            //无增广路，结束
  47.         for(int u = t; u != s; u = e[p[u]].from) {                  //修改残量网络
  48.             e[p[u]].flow += a[t];                                   //入弧流量增加
  49.             e[p[u]^1].flow -= a[t];                                 //反弧流量减少
  50.         }
  51.         flow += a[t];                                               //更新最大流
  52.     }
  53.     return flow;
  54. }

据说，反弧的作用是防止找到一条不够好的增广路而掐断了最好的增广路，类似于一剂“后悔药”。
但模拟的结果是几乎不会找到一条不好的增广路，所以我认为反弧是为了使最大流满足斜对称性（）。

Dinic

传统的EK算法复杂度为，实在是太慢了。所以我们考虑一个更好的算法——Dinic。
EK之所以慢，是因为这个算法每次只增广一条路，所以我们考虑一次性增广多条路。
我们考虑减少bfs的次数，转为使用dfs增广，bfs只是用来限制dfs的序。
每次bfs构造分层图，然后严格逐层增广，就可以达到的时间复杂度，实践中表现更好。

  1. inline int Dinic() {
  2.     int f = 0;
  3.     while (bfs()) {
  4.         f += dfs(s, INF);
  5.     }
  6.     return f;
  7. }
  9. inline bool bfs() {
  10.     memset(d, 0, sizeof(d));
  11.     qhd = qtl = 0;
  12.     q[qtl] = s;
  13.     qtl++;
  14.     d[s] = 1;
  15.     int tmp;
  16.     while (qhd < qtl) {
  17.         tmp = q[qhd % Q]; qhd++;
  18.         for (register int i = head[tmp]; i; i = next[i]) {
  19.             if (!d[to[i]] && cap[i] - flow[i] > 0) {
  20.                 d[to[i]] = d[tmp] + 1;
  21.                 q[qtl % Q] = to[i]; qtl++;
  22.             }
  23.         }
  24.         if (d[t]) return true;
  25.     }
  26.     return false;
  27. }
  29. int dfs(int x, int maxf) {
  30.     if (x == t) return maxf;
  31.     int f = 0, tmpf;
  32.     for (register int i = head[x]; i; i = next[i]) {
  33.         if (d[to[i]] == d[x] + 1 && cap[i] - flow[i] > 0) {
  34.             tmpf = dfs(to[i], min(maxf, cap[i] - flow[i]));
  35.             if (tmpf > 0) {
  36.                 flow[i] += tmpf;
  37.                 flow[i^1] -= tmpf;
  38.                 f += tmpf;
  39.                 maxf -= tmpf;
  40.             }
  41.         }
  42.     }
  43.     return f;
  44. }

最小费用最大流

Edmonds-Karp with SPFA

其实就是在找增广路的时候加上最短路即可

  1. //数据结构基本不变
  2. struct Edge {
  3.     int from, to, w, cap, flow; // 这里添加了费用w
  4.     Edge(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0) :
  5.         from(a), to(b), w(c), cap(d), flow(e) {}
  6. } e[M];
  7. int head[N], next[M], cnt = 1;
  8. int n, m, s, t;
  9. int a[N], p[N];
  10. int q[N], hd, tl, dis[N], inq[N]; // SPFA相关
  11. int flow, waste;
  13. inline void adde(int from, int to, int w, int flow) {
  14.     cnt++;
  15.     next[cnt] = head[from];
  16.     e[cnt] = Edge(from, to, w, flow, 0);
  17.     head[from] = cnt;
  18.     cnt++;
  19.     next[cnt] = head[to];
  20.     e[cnt] = Edge(to, from, -w, 0, 0); // 反边费用为相反数
  21.     head[to] = cnt;
  22. }
  24. inline void EK(int s, int t) {
  25.     flow = waste = 0; // 初始化流量和费用
  26.     while (1) { // 找增广路
  27.     //初始化
  28.         memset(inq, 0, sizeof(inq));
  29.         memset(dis, 0x3f, sizeof(dis));
  30.         memset(a, 0, sizeof(a));
  31.         memset(p, 0, sizeof(p));
  33.         hd = tl = 0;
  34.         q[tl++] = s;
  35.         dis[s] = 0;
  36.         inq[s] = 1;
  37.         a[s] = INF;
  38.     //  
  39.     //SPFA 过程
  40.         int tmp;
  41.         while (hd != tl) {
  42.             tmp = q[hd++ % N];
  43.             inq[tmp] = 0;
  44.             for (int i = head[tmp]; i; i = next[i]) {
  45.             //注意这里的条件与之前不同，这里是使用SPFA，所以一个点可以经过多次
  46.             //而由于最短路的性质，不会原地绕圈
  47.             //由于增广路的性质，这样不会丢失解，还能保证费用最小
  48.                 if (e[i].cap > e[i].flow && dis[tmp] + e[i].w < dis[e[i].to]) {
  49.                     dis[e[i].to] = dis[tmp] + e[i].w;
  50.                     a[e[i].to] = min(a[tmp], e[i].cap - e[i].flow);
  51.                     p[e[i].to] = i;
  52.                     if (!inq[e[i].to]) {
  53.                         q[tl++ % N] = e[i].to;
  54.                         inq[e[i].to] = 1;
  55.                     }
  56.                 }
  57.             }
  58.         }
  59.     //  
  60.         if (dis[t] == INF) break; // 无法增广 结束
  61.     // 更新   
  62.         for (int i = t; i != s; i = e[p[i]].from) {
  63.             e[p[i]].flow += a[t];
  64.             e[p[i]^1].flow -= a[t];
  65.         }
  66.         flow += a[t];
  67.         waste += a[t] * dis[t];
  68.     //
  69.     }
  70. }

经典模型

二分图最大匹配

添加超级源点与汇点，边容量为1，跑最大流。

DAG最小无交路径覆盖

将一个点拆成两个点，有向边转化成二分图，跑最大匹配。
解释：先将每个点看作一条路径，每个匹配将两条路径合为一条。由于匹配的性质，这些路径不会有交。

24题题解

1.飞行员配对方案

二分图最大匹配

每条匹配建一条容量为1的弧，超级源点向每个“英国飞行员”建一条容量为1的弧，每个“外籍飞行员”向超级汇点建一条容量为1的弧。

暴力搜索输出方案。

  1. inline void print() {
  2.     for (int i = head[0]; i; i = next[i]) {
  3.         if (e[i].flow == 1) {
  4.             printf("%d ", e[i].to);
  5.             for (int j = head[e[i].to]; j; j = next[j]) 
  6.                 if (e[j].flow == 1) printf("%d\n", e[j].to);
  7.         }
  8.     }
  9. }
  11. int main() {
  12.     scanf("%d %d", &n, &m);
  13.     for (int i = 0, j = 0; i != -1 && j != -1;) {
  14.         scanf("%d %d", &i, &j);
  15.         adde(i, j, 1);  
  16.     }
  17.     for (int i = 1; i <= n; ++i) adde(0, i, 1);
  18.     for (int i = 1; i <= m; ++i) adde(n+i, n+m+1, 1);
  19.     printf("%d\n", EK(0, n+m+1));
  20.     print();
  21.     return 0;
  22. }

2.

3.最小路径覆盖问题

经典套路，直接做。

  1. int main() {
  2.     scanf("%d%d", &n, &m);
  3.     s = 1; t = (n<<1|1) + 1;
  4.     for (int i = 1, x, y; i <= m; ++i) {
  5.         scanf("%d%d", &x, &y);
  6.         adde(x<<1, y<<1|1, 1);
  7.     }
  8.     for (int i = 1; i <= n; ++i) {
  9.         adde(s, i<<1, 1);
  10.         adde(i<<1|1, t, 1);
  11.     }
  12.     int ans = n - Dinic();
  13.     // 以下为输出方案，仅对较弱数据有效，慎重参考
  14.     int j = 2;
  15.     for (int i = 1; i <= ans; ++i) {
  16.         for (; j < t; j += 2) if (!vis[j]) {
  17.             print(j);
  18.             break;
  19.         }
  20.         printf("\n");
  21.     }
  22.     printf("%d\n", ans);
  23.     return 0;
  24. }

4.魔术球问题

考虑将能连成完全平方数的数建一条从较小的数连向较大的数的边，将问题转化为最小路径覆盖。动态加边。

  1. int main() {
  2.     int ans = 0;
  3.     while(1) {
  4.         m++;
  5.         adde(s, m << 1, 1);
  6.         adde(m << 1 | 1, t, 1);
  7.         for (int i = sqrt(2*m + 1); i; --i) {
  8.             int k = i * i - m;
  9.             if (k > 0 && k < m) {
  10.                 adde(k<<1, m<<1|1, 1);
  11.             }
  12.         }
  13.         ans = ans + 1 - Dinic();
  14.         if (ans > n) {
  15.             printf("%d\n", m - 1);
  16.             for (int i = 1; i <= n; ++i) {
  17.                 for (int j = 1; j <= m; ++j) {
  18.                     if (!vis[j]) {
  19.                         print(j);
  20.                         printf("\n");
  21.                         break;
  22.                     }
  23.                 }
  24.             }
  25.             break;
  26.         }
  27.     }
  28.     return 0;
  29. }

这个题也可以贪心，这启示我们不要被已有算法束缚。

8.机器人路径规划问题

不可做！！！！！

24.骑士共存问题

考虑转化问题，将其转化为选出一组点，使得任意两点间不能攻击。

考虑将棋盘黑白染色后，每个节点只能到达与其异色的节点，那么，可以将黑点连向S，白点连向T，两个能攻击的点之间连一条边，容量为INF(?)。

原问题转化为求二分图最小割（=最大匹配），再用所有点减去最小割即可。

处理走马有小技巧。

  1. // 走马方式
  2. int XX[] = {-2, -2, -1, -1, +1, +1, +2, +2};
  3. int YY[] = {-1, +1, -2, +2, -2, +2, -1, +1};
  5. int main() {
  6.     scanf("%d%d", &n, &m);
  7.     for (int i = 1, x, y; i <= m; ++i) {
  8.         scanf("%d%d", &x, &y);
  9.         a[x][y] = 1;
  10.     }
  11.     s = 0; t = n * n + 1;
  12.     for (int i = 1; i <= n; ++i) {
  13.         for (int j = 1; j <= n; ++j) {
  14.             int k = (i-1) * n + j;
  15.             if (!a[i][j]) {
  16.                 if ((i + j) & 1) {
  17.                     adde(s, k, 1);
  18.                     // 走马小技巧
  19.                     for (int aha = 0, wx, wy; aha <= 7; ++aha) {
  20.                         wx = i+XX[aha]; wy = j+YY[aha];
  21.                         if (!a[wx][wy] && wx > 0 && wx <= n && wy > 0 && wy <= n)
  22.                             adde(k, (wx-1)*n+wy, 1);
  23.                     }
  24.                 }
  25.                 else adde(k, t, 1);
  26.             }
  27.         }
  28.     }
  29.     printf("%d\n", n * n - Dinic() - m); // 这里一定要减去m!!!
  30.     return 0;
  31. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注