題目鏈接：點擊查看

題目大意：給出一張 n * m 的稠密圖，求以點 ( 1 , 1 ) 為起點，點 ( n , m ) 為終點的最小割

題目分析：n 和 m 都是 1e3 級別的，最多可能有 1e6 個點，3e6 條邊，跑最大流顯然是正確的，但是時間復雜度肯定是頂不住的，正確做法應該是將其轉換為對偶圖然后跑最短路，注意建邊是無向邊

講解博客：https://www.cnblogs.com/jinkun113/p/9495308.html

我的建圖方法是先將每個點預處理標號，下面圖中紅色是原來的點，藍色是對偶圖中的點

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e6+100;//頂點數 const int M=6e6+100;//邊數 struct Edge {int to,w,next; }edge[M];int head[N],d[N],cnt,n,m,id[1100][1100][2];//鏈式前向星 bool vis[N];void addedge(int u,int v,int w) {edge[cnt].to=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++;edge[cnt].to=u;edge[cnt].w=w;edge[cnt].next=head[v];head[v]=cnt++; }struct Node {int to,w;Node(int TO,int W){to=TO;w=W;}bool operator<(const Node& a)const{return w>a.w;} };void Dijkstra(int st) {priority_queue<Node>q;memset(vis,false,sizeof(vis));memset(d,inf,sizeof(d));d[st]=0;q.push(Node(st,0));while(q.size()){Node cur=q.top();int u=cur.to;q.pop();if(vis[u])continue;vis[u]=true;for(int i=head[u];i!=-1;i=edge[i].next)//掃描出所有邊 {int v=edge[i].to;int w=edge[i].w;if(d[v]>d[u]+w)//更新 {d[v]=d[u]+w;q.push(Node(v,d[v]));}}} }void init() {memset(head,-1,sizeof(head));cnt=0;int tot=0;for(int i=1;i<n;i++)for(int j=1;j<m;j++){id[i][j][0]=++tot;id[i][j][1]=++tot;} }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);scanf("%d%d",&n,&m);init();int st=N-1,ed=st-1;for(int i=1;i<=n;i++)//橫邊 for(int j=1;j<m;j++){int w;scanf("%d",&w);if(i==1)addedge(id[1][j][0],ed,w);else if(i==n)addedge(st,id[n-1][j][1],w);elseaddedge(id[i][j][0],id[i-1][j][1],w); }for(int i=1;i<n;i++)//豎邊 for(int j=1;j<=m;j++){int w;scanf("%d",&w);if(j==1)addedge(st,id[i][1][1],w);else if(j==m)addedge(id[i][m-1][0],ed,w);elseaddedge(id[i][j-1][0],id[i][j][1],w);}for(int i=1;i<n;i++)for(int j=1;j<m;j++){int w;scanf("%d",&w);addedge(id[i][j][1],id[i][j][0],w);}Dijkstra(st);printf("%d\n",d[ed]);return 0; }

?

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的洛谷 - P4001 [ICPC-Beijing 2006]狼抓兔子(网格图最大流转换为对偶图最短路)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。