LiRewriter
2017-12-14 21:47:20
看到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...不愧是玄学。
#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代码：
#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