BZOJ1001/LG4001「ICPCBeijing2006」狼抓兔子平面图最小割转对偶图最短路

问题描述

BZOJ1001

LG4001

题解

平面图最小割=对偶图最短路

假设起点和终点间有和其他边都不相交的一条虚边。

如图，平面图的若干条边将一个平面划分为若干个图形，每个图形就是对偶图中的一个点。

对偶图中的每一个点，和它在平面图中每一个相邻的图形间有边，边权为原来分开它们的边的边权。

于是平面图最小割就是对偶图最短路。

\(\mathrm{Code}\)

#include
using namespace std;
const int maxn=2*1000*1000+7;
int n,m,S,T;
int Head[maxn],to[maxn*3],Next[maxn*3],tot=1,w[maxn*3];
void addedge(int x,int y,int z){
to[++tot]=y,Next[tot]=Head[x],Head[x]=tot,w[tot]=z;
}
void add(int x,int y,int z){
addedge(x,y,z);addedge(y,x,z);
}
void Init(void){
scanf("%d%d",&n,&m);
}
int id(int x,int y,int type){
return (x-1)*(m-1)+y+(type-1)*(n-1)*(m-1);
}
void Hori(void){
for(int i=1,x;i scanf("%d",&x);
add(S,id(1,i,1),x);
}
for(int i=2,x;i for(int j=1;j scanf("%d",&x);
add(id(i-1,j,2),id(i,j,1),x);
}
}
for(int i=1,x;i scanf("%d",&x);
add(id(n-1,i,2),T,x);
}
}
void Longi(void){
for(int i=1,x;i scanf("%d",&x);add(T,id(i,1,2),x);
for(int j=2;j scanf("%d",&x);
add(id(i,j-1,1),id(i,j,2),x);
}
scanf("%d",&x);add(id(i,m-1,1),S,x);
}
}
void Obli(void){
for(int i=1;i for(int j=1,x;j scanf("%d",&x);
add(id(i,j,1),id(i,j,2),x);
}
}
}
void Graph_build(void){
S=(n-1)*(m-1)*2+1,T=S+1;
Hori();
Longi();
Obli();
}
int dis[maxn];
bool vis[maxn];
#define pii(x,y) make_pair(x,y)
void dijkstra(void){
memset(dis,0x3f,sizeof(dis));
priority_queue >q;
q.push(pii(0,S));dis[S]=0;
while(!q.empty()){
int x=(q.top()).second;q.pop();
if(vis[x]) continue;vis[x]=1;
if(x==T) return;
for(int i=Head[x];i;i=Next[i]){
int y=to[i];
if(dis[y]>dis[x]+w[i]){
dis[y]=dis[x]+w[i];
q.push(pii(-dis[y],y));
}
//if(y==T) return;
}
}
}
void One(void){
int ans=0x3f3f3f3f,x;
for(int i=1;i<=n;i++) for(int j=1;j scanf("%d",&x);ans=min(ans,x);
}
for(int i=1;i scanf("%d",&x);ans=min(ans,x);
}
printf("%d\n",ans);
}
void Work(void){
if(n==1||m==1){
One();return;
}
Graph_build();
dijkstra();
printf("%d\n",dis[T]);
}
int main(){
Init();
Work();
return 0;
}