网络流学习笔记（三） 最小割 平面图转对偶图

看到luogu4001竟然是BZOJ1001...惊了，明明前几天还没有来着 最大流算法的实现见前篇：https://www.luogu.org/blog/LittleRewriter/wang-lao-liu-er-zui-tai-liu-suan-fa-di-shi-xian 看到luogu上有了狼抓兔子就兴奋的交一发（雾） ## 最小割最大流定理 搜了一圈没有找到什么是最小割，然后懵逼了。 嗯...... 首先，什么是割？其实，割=割边=去掉以后使图不连通的边的集合 然后，容量和最少的割集称为最小割。 对于割，有这样一个重要定理： > 最小割=最大流 嗯，最小割就这么多东西。 为什么正确？这里给出一种直观的想法 （原PO：https://jecvay.com/2014/11/what-is-min-cut.html） >1.最大流不可能大于最小割, 因为最大流所有的水流都一定经过最小割那些割边, 流过的水流怎么可能比水管容量还大呢? 2.最大流不可能小于最小割, 如果小, 那么说明水管容量没有物尽其用, 可以继续加大水流. 证毕。 这里首先说一个技巧，无向图的网络流在建边时反向弧直接建成权值为v的边即可，因为这样的边一开始就是可以增广的。 题意是求一个无向图的最小割，然后我们运用最小割-最大流定理，可以转化成求最大流的问题。不过朴素的Dinic是会TLE的，这里提供一种优化方法： 我们知道，假定在一次dinic过程中，发现不能再进行增广了，那么就相当于向下的这条路是废的。因此，我们可以直接把这条路堵上，然后就可以过了。优化效果很明显，BZOJ上TLE->1644msAC（虽然我质疑出题人可能专门卡了朴素的Dinic），洛谷直接0ms...不愧是玄学。 ```cpp #include <iostream> #include <cstdio> #include <queue> #include <cstring> #include <cctype> using namespace std; inline void read(int &x) { x = 0; char c = getchar(); while(!isdigit(c)) c = getchar(); while(isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); } #define MAXN 1003 struct node{ int fr, to, va, nxt; }edge[MAXN * MAXN * 6]; int head[MAXN * MAXN], cnt; inline void add_edge(int u, int v, int w) { edge[cnt].fr = u, edge[cnt].to = v, edge[cnt].va = w; edge[cnt].nxt = head[u], head[u] = cnt++; edge[cnt].fr = v, edge[cnt].to = u, edge[cnt].va = w; edge[cnt].nxt = head[v], head[v] = cnt++; //反向边初始化 } int st, ed, rank[MAXN * MAXN]; int BFS() { queue<int> q; memset(rank, 0, sizeof rank); rank[st] = 1; q.push(st); while(!q.empty()) { int tmp = q.front(); //cout<<tmp<<endl; q.pop(); for(int i = head[tmp]; i != -1; i = edge[i].nxt) { int o = edge[i].to; if(rank[o] || edge[i].va <= 0) continue; rank[o] = rank[tmp] + 1; q.push(o); } } return rank[ed]; } int dfs(int u, int flow) { if(u == ed) return flow; int add = 0; for(int i = head[u]; i != -1 && add < flow; i = edge[i].nxt) { int v = edge[i].to; if(rank[v] != rank[u] + 1 || !edge[i].va) continue; int tmpadd = dfs(v, min(edge[i].va, flow - add)); if(!tmpadd) { //重要！就是这里！ rank[v] = -1; continue; } edge[i].va -= tmpadd, edge[i ^ 1].va += tmpadd; add += tmpadd; } return add; } int ans; void dinic() { while(BFS()) ans += dfs(st, 0x3fffff); } int n, m; inline int gethash(int i, int j) { return (i - 1) * m + j; } int main() { memset(head, -1, sizeof head); read(n), read(m); int tmp; st = 1, ed = gethash(n, m); for(int i = 1; i <= n; ++i) { for(int j = 1; j < m; ++j) read(tmp), add_edge(gethash(i, j), gethash(i, j + 1), tmp); } for(int i = 1; i < n; ++i) { for(int j = 1; j <= m; ++j) read(tmp), add_edge(gethash(i, j), gethash(i + 1, j), tmp); } for(int i = 1; i < n; ++i) { for(int j = 1; j < m; ++j) read(tmp), add_edge(gethash(i, j), gethash(i + 1, j + 1), tmp); } dinic(); cout<<ans<<endl; return 0; } ``` --- ## 平面图与对偶图 仍然考虑狼抓兔子。不得不说，网络流这种玄学算法总会让人思考人生。于是机智的人做了这样一件事。 先来观察下面的这张图：  我们发现，这么一张图，可以转化成任意两边的交点都在顶点上的形式。  下面的这张却完全不行。 像这样任意两边的交点在顶点上的图我们称为平面图。 几条边围成一个区域，这个区域称为一个面。 对平面图，我们定义对偶图：  下图中黑色的是个平面图，红色的就是对偶图。其建立方法是，对每个面建一个点，只要有一条边是在两个面之间，我们就对这两个面对应的点连边（稍有些绕）。注意是有一条边就连线。 然后我们就得到萌萌哒的对偶图一张！ 对偶图就有很多美妙的性质了。比如说，我们发现，对偶图的一条边就对应了一条割边。 既然如此的话，想想狼抓兔子，一条割边有一个容量，那么如果我们建它的对偶图，最短路就是最小割。 所以得出下面的重要定理： > 对平面图来说，最大流 = 最小割 = 对偶图最短路 所以我们就可以稳一些跑出来狼抓兔子。 （详细的图解：https://www.cnblogs.com/jinkun113/p/4682827.html） 于是AC代码： ```cpp #include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <cctype> #include <vector> #include <cstring> using namespace std; inline void read(int &x) { x = 0; char c = getchar(); while(!isdigit(c)) c = getchar(); while(isdigit(c)) x = x * 10 + c - '0', c = getchar(); } #define MAXN 2000010 struct node{ int to, va; node(int a, int b) { to = a, va = b; } }; vector<node> v[MAXN]; inline void add_edge(int f, int t, int w) { v[f].push_back(node(t, w)); v[t].push_back(node(f, w)); } bool vis[MAXN]; int st, ed; int dis[MAXN]; int SPFA() { memset(dis, 0x3f, sizeof dis); vis[st] = 1; queue<int> q; q.push(st); dis[st] = 0; while(!q.empty()) { int tmp = q.front(); //cout<<tmp<<" "; q.pop(); vis[tmp] = 0; for(int i = 0; i < v[tmp].size(); ++i) { int o = v[tmp][i].to; //cout<<o<<" "; if(dis[o] > dis[tmp] + v[tmp][i].va) { dis[o] = dis[tmp] + v[tmp][i].va; if(!vis[o]) q.push(o), vis[o] = 1; } } } return dis[ed]; } int n, m; inline void getheng(int i, int j, int k) { if(i == 1) add_edge(st, j, k); else if(i == n) add_edge((2 * (n - 1) - 1) * (m - 1) + j, ed, k); else add_edge((2 * (i - 1) - 1) *(m - 1) + j, 2 * (i - 1) * (m - 1) + j, k); } inline void getshu(int i, int j, int k) { if(j == 1) add_edge((i * 2 - 1) * (m - 1) + 1, ed, k); else if(j == m) add_edge(st, 2 * i * (m - 1) - (m - 1), k); else add_edge((i - 1) * 2 * (m - 1) + j - 1, ((i - 1) * 2 + 1) * (m - 1) + j, k); } inline void getxie(int i, int j, int k) { add_edge((i - 1) * 2 * (m - 1) + j, (i - 1) * 2 * (m - 1) + (m - 1) + j, k); } int main() { read(n), read(m); st = (n - 1) * (m - 1) * 2 + 1, ed = (n - 1) * (m - 1) * 2 + 2; int x; for(int i = 1; i <= n; ++i) { for(int j = 1; j < m; ++j) read(x), getheng(i, j, x); } for(int i = 1; i < n; ++i) { for(int j = 1; j <= m; ++j) read(x), getshu(i, j, x); } for(int i = 1; i < n; ++i) { for(int j = 1; j < m; ++j) read(x), getxie(i, j, x); } /*for(int i = 1; i <= ((n - 1) * (m - 1) * 2 + 2); ++i) { for(int j = 0; j < v[i].size(); ++j) cout<<v[i][j].to<<" "; cout<<endl; }*/ cout<<SPFA()<<endl; return 0; } ``` 建图建到吐血...真的心累啊... BZOJ3464ms，比网络流玄学还要慢些？好吧...luogu更夸张，直接700多ms... --- 嗯，费用流的问题月考后再说 ## 参考资料 https://wenku.baidu.com/view/8c887f10a6c30c2259019ea0.html https://www.cnblogs.com/ljh2000-jump/p/5503061.html http://hzwer.com/1261.html http://blog.csdn.net/ff88655068/article/details/38878343