本文主要是介绍HDU 3035 War 平面最小割+优先队列优化的dij，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给一个矩形图（具体看图），左上角的点为起点，右下角的点为终点。图中每一条边都有权值，所以要是想切断一些边，使得起点终点不能相通，问需要切掉边的最小权值。
想法：网络流最小割当然可以做，但是点有501*501+500*500，很尴尬太多了。所以可以从左下角，向右上角切割来阻断路径（平面最小割）。这个要把每一个被线分割的区域当做一个点，每个区域之间的线的权值为边的权值。这个里面有一个类似的图HDU 3870 Catch the Theves 最短路求最小割
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define inf 0x7fffffff
using namespace std;
const int nodes=505*505*5;
const int edges=505*505*16;
int n,m,st,ed;
int hang[505][505],shu[505][505],cha[1005][1005];
int vis[nodes],dis[nodes];
struct node
{int v,next,w;
}e[edges];
struct nodee
{int v,dis;nodee() {}nodee(int v1,int dis1):v(v1),dis(dis1){}bool operator < (const nodee a)const{return a.dis<dis;}
};
int head[nodes],cnt;
void Init()
{memset(head,-1,sizeof(head));cnt=0;
}
void add(int a,int b,int c)
{e[cnt].v=b;e[cnt].w=c;e[cnt].next=head[a];head[a]=cnt++;
}
void build_map()
{st=0;ed=n*m*4+1;for(int i=1;i<=n;i++)//左边 {int num=2*n*m+((i-1)*m+1)*2-1;add(st,num,shu[i][1]);}for(int i=1;i<=n;i++)//右边 {int num=2*n*m+((i-1)*m+m)*2;add(num,ed,shu[i][m+1]);}for(int i=1;i<=m;i++)//下边 {int num=(2*n-1)*m+i;add(st,num,hang[n+1][i]);}for(int i=1;i<=m;i++)//上边 {int num=(2*1-1)*m+i-m;add(num,ed,hang[1][i]);}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int numz=2*n*m+((i-1)*m+j)*2-1;int numy=2*n*m+((i-1)*m+j)*2;int nums=(2*i-1)*m+j-m;int numx=(2*i-1)*m+j;add(numz,nums,cha[2*i-1][2*j-1]);add(numy,nums,cha[2*i-1][2*j]);add(numx,numz,cha[2*i][2*j-1]);add(numx,numy,cha[2*i][2*j]);add(nums,numz,cha[2*i-1][2*j-1]);add(nums,numy,cha[2*i-1][2*j]);add(numz,numx,cha[2*i][2*j-1]);add(numy,numx,cha[2*i][2*j]);if(j!=m){add(numy,numy+1,shu[i][j+1]);add(numy+1,numy,shu[i][j+1]);}if(i!=1){add(nums,nums-m,hang[i][j]);add(nums-m,nums,hang[i][j]);}}}
}
void dij()
{for(int i=st;i<=ed;i++){dis[i]=inf;vis[i]=0;}dis[st]=0;priority_queue<nodee>q;q.push(nodee(st,0));while(!q.empty()){int u=q.top().v;q.pop();if(u==ed) break;if(vis[u]) continue;vis[u]=1;for(int i=head[u];i+1;i=e[i].next){int v=e[i].v;if(!vis[v]&&dis[v]>dis[u]+e[i].w){dis[v]=dis[u]+e[i].w;q.push(nodee(v,dis[v]));}}}printf("%d\n",dis[ed]);
}
int main()
{while(~scanf("%d%d",&n,&m)){for(int i=1;i<=n+1;i++)//(n+1)*m{for(int j=1;j<=m;j++)scanf("%d",&hang[i][j]);}for(int i=1;i<=n;i++)//n*(m+1){for(int j=1;j<=m+1;j++)scanf("%d",&shu[i][j]);}for(int i=1;i<=2*n;i++)//2n*2m {for(int j=1;j<=2*m;j++)scanf("%d",&cha[i][j]);}Init();build_map(); dij();}return 0;}
这篇关于HDU 3035 War 平面最小割+优先队列优化的dij的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
