題面
題意
給出一幅無向平面圖,求s到t的最小割.
對偶圖:将原圖中的每一塊區域當作一個點,原圖上的每一條邊轉化為這條邊兩邊區域之間的一條邊,任何隻在頂點處有交點的圖(平面圖)都有對偶圖.
做法
這道題如果直接跑最大流,複雜度顯然不對,但因為它存在對偶圖,我們可以将題目轉化為求左下角這塊到右上角這塊的最短路,對于樣例可以這麼建圖
首先建對偶圖
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiI0NXYFhGd192UvwVe0lmdhJ3ZvwFM38CXlZHbvN3cpR2Lc1TPB10QGtWUCpEMJ9CXsxWam9CXwADNvwVZ6l2c052bm9CXUJDT1wkNhVzLcRnbvZ2Lc1TPBV2cshVZ1AHWlZXUYpVd1kmYr50MZV3YyI2cKJDT29GRjBjUIF2LcRHelR3LcJzLctmch1mclRXY39zNxUjNwYTNwEzMyQDM4EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
之後去掉原圖就可以得到
可以發現從0點到13點((n-1)*(m-1) *2+1)的最短路恰好為最小割,這也是對偶圖的一個性質,是以隻要跑一邊迪傑斯特拉即可.
代碼
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define C ch=getchar()
#define INF 0x3f3f3f3f
#define P pair<int,int>
#define mp make_pair<int,int>
#define fi first
#define se second
#define N 1000100
using namespace std;
int n,m,first[N<<],bb,t,s,d[N<<];
bool vis[N<<];
char ch;
P tmp;
struct Bn
{
int to,next,quan;
} bn[N*];
priority_queue<P,vector<P>,greater<P> >pq;
inline int read()
{
int res;
for(C;ch<'0';C);
for(res=ch-'0',C;ch>='0';res=res*+ch-'0',C);
return res;
}
inline int ask(int u,int v,int w)
{
return (u-)*(n-)*+(v-)*+w+;
}
inline void add(int u,int v,int w)
{
bb++;
bn[bb].to=v;
bn[bb].next=first[u];
bn[bb].quan=w;
first[u]=bb;
}
inline void ad(int u,int v,int w)
{
add(u,v,w);
add(v,u,w);
}
int main()
{
memset(first,-,sizeof(first));
int i,j,p,q;
m=read(),n=read();
t=(m-)*(n-)*+;
for(i=; i<=m; i++)
{
for(j=; j<n; j++)
{
p=read();
i==?ad(ask(,j,),t,p):i==m?ad(ask(m-,j,),s,p):ad(ask(i-,j,),ask(i,j,),p);
}
}
for(i=; i<m; i++)
{
for(j=; j<=n; j++)
{
p=read();
j==?ad(s,ask(i,j,),p):j==n?ad(ask(i,n-,),t,p):ad(ask(i,j-,),ask(i,j,),p);
}
}
for(i=; i<m; i++)
{
for(j=; j<n; j++)
{
ad(ask(i,j,),ask(i,j,),read());
}
}
memset(d,,sizeof(d));
pq.push(mp(,s));
d[s]=;
for(; !pq.empty()&&!vis[t];)
{
tmp=pq.top();
pq.pop();
q=tmp.se;
if(vis[q]) continue;
vis[q]=;
for(p=first[q]; p!=-; p=bn[p].next)
{
if(d[bn[p].to]>d[q]+bn[p].quan)
{
d[bn[p].to]=d[q]+bn[p].quan;
pq.push(mp(d[bn[p].to],bn[p].to));
}
}
}
cout<<d[t];
}