题目传送门(BZOJ)
>原文链接<

题解 :

这篇文章有一个假标题

题意就是求一个最小割, 那我们就求一个最小割咯.

细心的你一定发现这个东西用dinic跑不下来, 然后我们需要转成对偶图最短路.

但是不细心的我并没有看数据范围, 直接连边跑dinic就过了

你看, 非常好写 (老脸一红

代码 :

#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>#include <queue>using namespace std;const int N =1e6;const int inf = 0x3f3f3f3f;#define P(i, j) (((i)-1)*m+(j))int head[N+10], to[N*6+10], val[N*6+10], next[N*6+10];int cnt = 1;int dep[N+10];int n, m, s, t;void add_edge(int a, int b, int c) { to[++cnt] = b; next[cnt] = head[a]; head[a] = cnt; val[cnt] = c; to[++cnt] = a; next[cnt] = head[b]; head[b] = cnt; val[cnt] = c;}queue<int>q;bool bfs() { memset(dep, 0, sizeof(dep)); while(!q.empty())q.pop(); q.push(s); dep[s]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i;i=next[i]) { if(!dep[to[i]]&&val[i]) { dep[to[i]]=dep[u]+1; if(to[i]==t)return 1; q.push(to[i]); } } } return 0;}int dfs(int p, int mf) { int nf = 0; if(p==t)return mf; for(int i = head[p]; i; i = next[i] ) { if(dep[to[i]]==dep[p]+1&&val[i]) { int tmp=dfs(to[i], min(mf-nf, val[i])); if(!tmp)dep[to[i]]=0; nf+=tmp; val[i]-=tmp; val[i^1]+=tmp; if(nf==mf)break; } } return nf;}void dinic() { int ans=0, tmp=0; while(bfs()) { while(tmp=dfs(s, inf)) ans+=tmp; } printf("%d\n", ans);}int main() { scanf("%d%d", &n, &m); s = n*m+1, t = n*m+2; for(int i = 1; i <= n; i ++ ) for(int j = 1; j < m; j ++ ) { int x; scanf("%d", &x); add_edge(P(i, j), P(i, j+1), x); } for(int i = 1; i < n; i ++ ) for(int j = 1; j <= m; j ++ ) { int x; scanf("%d", &x); add_edge(P(i, j), P(i+1, j), x); } for(int i = 1; i < n; i ++ ) for(int j = 1; j < m; j ++ ) { int x; scanf("%d", &x); add_edge(P(i, j), P(i+1, j+1), x); } add_edge(s, 1, inf); add_edge(P(n, m), t, inf); dinic();}