【BZOJ1001】狼抓兔子（平面图转对偶图，最短路）

时间：2023-03-10 01:56:58
【BZOJ1001】狼抓兔子（平面图转对偶图，最短路）

【BZOJ1001】狼抓兔子（平面图转对偶图，最短路）

题面

BZOJ

洛谷

题解

这题用最小割可以直接做

今天再学习了一下平面图转对偶图的做法

大致的思路如下：

1.将源点到汇点中再补一条不与任何线段有交点的边。这条边把外侧无限大的区域划分为了两部分，一部分为\(S\)面，另外一部分为\(T\)面。

2.平面图的任何一条边一定只与两个面相连，将这两个边相连，权值为边的边权

此时\(S->T\)的最短路就是原来平面图中的最小割

伪证如下：

如果在对偶图上走了一条边，必定将原图中的一条边给割开

考虑一条\(S->T\)的路径，

一定沿着\(S\)平面割开了若干平面，使得\(S\)平面与\(T\)平面相连

因此，一条路径是原图中的一个割

割的大小就是路径的长度

因此，最小割就是对偶图上的最短路

代码如下：

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 2222222

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

struct Line{int v,next,w;}e[6666666];

int h[MAX],cnt=1;

inline void Add(int u,int v,int w){e[cnt]=(Line){v,h[u],w};h[u]=cnt++;}

priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >Q;

pair<int,int> u;

int dis[MAX],T;

bool vis[MAX];

int Dijkstra(int S)

{

	Q.push(make_pair(0,S));

	while(!Q.empty())

	{

		u=Q.top();Q.pop();

		if(vis[u.second])continue;

		dis[u.second]=u.first;vis[u.second]=true;

		for(int i=h[u.second];i;i=e[i].next)

			if(!vis[e[i].v])Q.push(make_pair(u.first+e[i].w,e[i].v));

	}

	return dis[T];

}

int p[2222][1111],tot;

int n,m,S;

int main()

{

	n=read();m=read();

	for(int i=1;i<=n+n-2;++i)

		for(int j=1;j<m;++j)

			p[i][j]=++tot;

	T=tot+1;

	for(int i=1,id=1;i<=n;++i,id+=2)

		for(int j=1;j<m;++j)

		{

			int w=read(),u=S,v=T;

			if(i!=1)v=p[id-1][j];

			if(i!=n)u=p[id][j];

			Add(u,v,w);Add(v,u,w);

		}

	for(int i=1,id=1;i<n;++i,id+=2)

		for(int j=1;j<=m;++j)

		{

			int w=read(),u=S,v=T;

			if(j!=1)u=p[id][j-1];

			if(j!=m)v=p[id+1][j];

			Add(u,v,w);Add(v,u,w);

		}

	for(int i=1,id=1;i<n;++i,id+=2)

		for(int j=1;j<m;++j)

		{

			int w=read(),u=p[id][j],v=p[id+1][j];

			Add(u,v,w);Add(v,u,w);

		}

	printf("%d\n",Dijkstra(0));

	return 0;

}

相关文章