题目大意
源点为 (1,1),汇点为 (n,m) (上图中n=4,m=4)。有以下三种类型的道路
(x, y) <==> (x+1, y)
(x, y) <==> (x, y+1)
(x, y) <==> (x+1, y+1)
每条无向边边权>0,求最小割。
数据范围
$1\leqslant n,m\leqslant 1000$
题解
平面图最大流
可以把每一个面作为一个点,如果原图一条边$k$分割了两个面$A,B$
那么从A向B连一条无向边,边权与边$k$边权相等
把外平面分成两个平面,一个作为起点一个作为终点,同样建边
要求是使得新图的一条路径对应原图的一个割
那么跑一次最短路就等于原图的最小割。
关于平面图最大流的知识可以看《两极相通——浅析最大—最小定理在信息学竞赛中的应用》
程序
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
#define inf 0x3f3f3f3f
#define maxn 3000000
using namespace std;
struct edge{int to,next,c;}e[maxn*2+500];
int last[maxn+500];
int flag[maxn+500],dis[maxn+500];
int n,m,et,nm,u,v,tot;
inline void addedge(int u,int v,int c){
e[++et].to=v;e[et].next=last[u];e[et].c=c;last[u]=et;
e[++et].to=u;e[et].next=last[v];e[et].c=c;last[v]=et;
}
inline void spfa(){
queue <int> q;
memset(dis,inf,sizeof(dis));
q.push(0);dis[0]=0;flag[0]=1;
while(!q.empty()){
int h=q.front();q.pop();flag[h]=0;
goedge(i,h)
if (dis[h]+e[i].c<dis[e[i].to]){
dis[e[i].to]=dis[h]+e[i].c;
if (!flag[e[i].to]){flag[e[i].to]=1;q.push(e[i].to);}
}
}
}
int main(){
scanf("%d%d",&n,&m);
nm=2*(n-1)*(m-1)+1;
For(i,1,n)
For(j,1,m-1){
int c;scanf("%d",&c);++tot;
u=2*(tot-m+1);v=2*tot-1;
if (i==1) u=0;if (i==n) v=nm;
addedge(u,v,c);
}
tot=0;
For(i,1,n-1)
For(j,1,m){
int c;scanf("%d",&c);++tot;
u=2*tot-3;v=2*tot;
if (j==1) u=nm;if (j==m) {v=0;tot--;}
addedge(u,v,c);
}
tot=0;
For(i,1,n-1)
For(j,1,m-1){
int c;scanf("%d",&c);++tot;
u=2*tot-1;v=2*tot;
addedge(u,v,c);
}
spfa();
printf("%d\n",dis[nm]);
return 0;
}