正題

題目鏈接:https://www.luogu.com.cn/problem/P4001

---

題目大意

給出一個(gè)類似于

的網(wǎng)格圖，求起點(diǎn)到終點(diǎn)的最小割。

---

解題思路

最小割直接跑網(wǎng)絡(luò)流，然后發(fā)現(xiàn)$dinic$都過(guò)不了。（好像加點(diǎn)玄學(xué)優(yōu)化就能過(guò)）

然后上點(diǎn)科技，平面圖最小割轉(zhuǎn)其補(bǔ)圖（對(duì)偶圖）的最短路

• 平面圖：滿足所有邊不相交的情況下可以被畫(huà)在平面上的一張圖$G(V,E)$
• 對(duì)偶圖：將一張平面圖的各個(gè)區(qū)域變成一個(gè)點(diǎn)，然后平面圖上分割兩個(gè)區(qū)域$a,b$的邊在對(duì)偶圖上就是連接$a,b$的一條邊。

這題顯然是平面圖，轉(zhuǎn)換成對(duì)偶圖就是

畫(huà)的比較丑，將就著看把。

然后感性理解一下發(fā)現(xiàn)結(jié)論確實(shí)成立。

跑$dij$就好了

時(shí)間復(fù)雜度$O(nm\log (nm))$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define mp(x,y) make_pair(x,y) using namespace std; const int N=1010*1010*2; struct node{int to,next,w; }a[N<<4]; int n,m,s,t,tot,ls[N],f[N]; bool v[N]; priority_queue<pair<int ,int > >q; int p(int x,int y,int z) {return ((x-1)*m+y)*2-z;} void addl(int x,int y,int w){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=w;return; } int dij(){memset(f,0x3f,sizeof(f));f[s]=0;q.push(mp(0,s));while(!q.empty()){int x=q.top().second;q.pop();if(v[x])continue;v[x]=1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(f[x]+a[i].w<f[y]){f[y]=f[x]+a[i].w;q.push(mp(-f[y],y));}}}return f[t]; } int main() {scanf("%d%d",&n,&m);s=p(n-1,m-1,0)+1;t=s+1;for(int i=1;i<=n;i++)for(int j=1;j<m;j++){int x;scanf("%d",&x);if(i==1)addl(s,p(i,j,0),x);else if(i==n)addl(p(i-1,j,1),t,x);else addl(p(i-1,j,1),p(i,j,0),x);}for(int i=1;i<n;i++)for(int j=1;j<=m;j++){int x;scanf("%d",&x);if(j==1)addl(p(i,j,1),t,x);else if(j==m)addl(s,p(i,j-1,0),x);else addl(p(i,j,1),p(i,j-1,0),x);}for(int i=1;i<n;i++)for(int j=1;j<m;j++){int x;scanf("%d",&x);addl(p(i,j,0),p(i,j,1),x);}printf("%d\n",dij());return 0; }

總結(jié)

以上是生活随笔為你收集整理的P4001-[ICPC-Beijing 2006]狼抓兔子【对偶图】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。