题目
网格图最小割 \((n,m\leq 1000)\)
分析
首先网络流可以过, 但是由于无向图, 所以残量网络容量也为 \(w\),\(Dinic\) 玄学 AC, 代码就不贴了
那有没有其它方法呢, 网格图显然是一张平面图, 平面图可以把它变为对偶图, 在对偶图上跑最短路
建图比较玄学, 跑的比网络流慢
代码
- #include <cstdio>
- #include <cctype>
- #include <queue>
- #include <cstring>
- #define rr register
- using namespace std;
- const int N=2000011;
- struct node{int y,w,next;}e[N*6];
- int ls[N],dis[N],k=1,n,m,s,t,cnt;
- pair<int,int>heap[N];
- inline signed iut(){
- rr int ans=0,f=1; rr char c=getchar();
- while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
- while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
- return ans*f;
- }
- inline void add(int x,int y,int w){
- e[++k]=(node){y,w,ls[x]}; ls[x]=k;
- e[++k]=(node){x,w,ls[y]}; ls[y]=k;
- }
- inline void Get_Hang(int i,int j,int w){
- if (i==1) add(s,j,w);
- else if (i==n) add((2*n-3)*(m-1)+j,t,w);
- else add((2*i-3)*(m-1)+j,(2*i-2)*(m-1)+j,w);
- }
- inline void Get_Lie(int i,int j,int w){
- if (j==1) add((2*i-1)*(m-1)+1,t,w);
- else if (j==m) add(s,(2*i-1)*(m-1),w);
- else add((2*i-2)*(m-1)+j-1,(2*i-1)*(m-1)+j,w);
- }
- inline void Get_Xie(int i,int j,int w){
- add((2*i-2)*(m-1)+j,(2*i-1)*(m-1)+j,w);
- }
- inline void Push(pair<int,int>w){
- heap[++cnt]=w;
- rr int x=cnt;
- while (x>1){
- if (heap[x>>1]>heap[x])
- swap(heap[x>>1],heap[x]),x>>=1;
- else return;
- }
- }
- inline void Pop(){
- heap[1]=heap[cnt--];
- rr int x=1;
- while ((x<<1)<=cnt){
- rr int y=x<<1;
- if (y<cnt&&heap[y+1]<heap[y]) ++y;
- if (heap[y]<heap[x]) swap(heap[y],heap[x]),x=y;
- else return;
- }
- }
- inline signed Dijkstra(){
- memset(dis,42,sizeof(dis)); dis[s]=0;
- heap[++cnt]=make_pair(0,s);
- while (cnt){
- rr int x=heap[1].second,t=heap[1].first;
- Pop(); if (t!=dis[x]) continue;
- for (rr int i=ls[x];i;i=e[i].next)
- if (dis[e[i].y]>dis[x]+e[i].w){
- dis[e[i].y]=dis[x]+e[i].w;
- Push(make_pair(dis[e[i].y],e[i].y));
- }
- }
- return dis[t];
- }
- signed main(){
- n=iut(),m=iut(),s=(n-1)*(m-1)<<1|1,t=s+1;
- for (rr int i=1;i<=n;++i)
- for (rr int j=1;j<m;++j) Get_Hang(i,j,iut());
- for (rr int i=1;i<n;++i)
- for (rr int j=1;j<=m;++j) Get_Lie(i,j,iut());
- for (rr int i=1;i<n;++i)
- for (rr int j=1;j<m;++j) Get_Xie(i,j,iut());
- return !printf("%d",Dijkstra());
- }
- # 对偶图最短路, 网络流 #洛谷 4001 [ICPC-Beijing 2006] 狼抓兔子
来源: http://www.bubuko.com/infodetail-3433908.html