[洛谷 4001][ICPC-Beijing 2006]狼抓兔子

题目链接

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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注