目录
显示
题目链接
https://www.luogu.com.cn/problem/P4001
题解
本题可以直接在原图上跑最小割解决，时间复杂度为 \(O(n^3m^3)\)。
（然而 \(n,m \leq 1000\) 的时候网络流仍然能通过本题，而且实际效率很高）
如何优化这个复杂度呢？
如果我们把我们选择的所有边用一条线连接起来，就会发现这条线从上面/左面出发，到达下面/右面。这条线将图分割成了两部分，从而达到了最小割的目的。
于是引入对偶图最短路的概念。
在一个平面图中，我们将边围成的区域视为一个点，如果两个区域之间有一条边权为 \(w\) 的边相邻，则在这两个区域间连一条边权为 \(w\) 的边。
这样最小割就被我们转化成了对偶图上从左上方到右下方的最短路。
在对偶图中有 \(O(nm)\) 个点和边，所以时间复杂度为 \(O(nm \log nm)\)。
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct node
{
int x,y;
bool operator<(const node&a)const
{
return y>a.y;
}
};
struct edge
{
int v,w,next;
}e[10000005];
int a[1005][1005],b[1005][1005],c[1005][1005];
int n,m,s,t,cnt;
int dis[2000005],head[2000005],vis[2000005];
void addedge(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
int f(int x,int y,int z)
{
return z*(m-1)*n+(m-1)*(x-1)+y;
}
int dijkstra()
{
priority_queue<node> q;
memset(dis,63,sizeof(dis));
dis[s]=0;
q.push({s,0});
while(!q.empty())
{
int u=q.top().x;
q.pop();
if(vis[u])continue;
vis[u]=1;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w)
{
dis[v]=dis[u]+e[i].w;
if(!vis[v])q.push({v,dis[v]});
}
}
}
return dis[t];
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
s=2*n*m+1,t=2*n*m+2;
for(int i=1;i<=n;i++)
for(int j=1;j<m;j++)
cin>>a[i][j];
for(int i=1;i<n;i++)
for(int j=1;j<=m;j++)
cin>>b[i][j];
for(int i=1;i<n;i++)
for(int j=1;j<m;j++)
cin>>c[i][j];
for(int j=1;j<m;j++)
{
int v=f(1,j,0);
addedge(s,v,a[1][j]);
addedge(v,s,a[1][j]);
}
for(int i=2;i<n;i++)
for(int j=1;j<m;j++)
{
int u=f(i-1,j,1),v=f(i,j,0);
addedge(u,v,a[i][j]);
addedge(v,u,a[i][j]);
}
for(int j=1;j<m;j++)
{
int u=f(n-1,j,1);
addedge(u,t,a[n][j]);
addedge(t,u,a[n][j]);
}
for(int i=1;i<n;i++)
{
int u=f(i,1,1);
addedge(t,u,b[i][1]);
addedge(u,t,b[i][1]);
}
for(int i=1;i<n;i++)
for(int j=2;j<m;j++)
{
int u=f(i,j-1,0),v=f(i,j,1);
addedge(u,v,b[i][j]);
addedge(v,u,b[i][j]);
}
for(int i=1;i<n;i++)
{
int u=f(i,m-1,0);
addedge(s,u,b[i][m]);
addedge(u,s,b[i][m]);
}
for(int i=1;i<n;i++)
for(int j=1;j<m;j++)
{
int u=f(i,j,0),v=f(i,j,1);
addedge(u,v,c[i][j]);
addedge(v,u,c[i][j]);
}
cout<<dijkstra()<<endl;
return 0;
}