题意是给出一张网格图，每个点都延伸出横边，竖边，斜边，每条边都有一条权值，要求左上角到右下角的道路被隔断，问最小割。 对于最小割的题目，很自然地想到网络流，但此题n的范围并不小，用网络流效率不高。针对本题的特点，我们可以将该图进行转化，转化成其对偶图，然后在对偶图上求最短路即是原图的最小割。 如何进行对偶图转化？原图中的面—>新图中的点，对于原图中的每一条边e，属于两个面f1，f2，那么对应在新图中一条边（f1，f2），权值等于e的权值。 图转化完之后添加源点，汇点，建立源点到左边界和下边界的边，权值为0，建立上边界和右边界到汇点的边，权值为0。建图完毕。 在对偶图上跑一次Dijkstra，最短路距离即是最小割。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<queue>#define LL long longusing namespace std;const int maxn=2e6+5;const int Inf=0x3f3f3f3f;struct HeapNode{ int u, d; HeapNode(){} HeapNode(int a,int b):u(a),d(b){} bool Operator < (const HeapNode& rhs)const{ return d>rhs.d; }};struct Edge{ int to, next, d; Edge(){} Edge(int a,int b,int c):to(a),next(b),d(c){}};struct Dijkstra{ int n, m; int ecnt; Edge edges[3*maxn]; int head[maxn]; bool done[maxn]; int d[maxn]; int p[maxn]; void init(int n){ this->n=n; memset(head,-1,sizeof(head)); ecnt=0; } void AddEdge(int u,int v,int w){ // PRintf("u=%d v=%d w=%d/n",u, v, w); edges[ecnt]=Edge(v,head[u],w); head[u]=ecnt++; } void dijkstra(int s){ priority_queue<HeapNode> Q; for(int i=0;i<n;i++) d[i]=Inf; d[s]=0; memset(done,0,sizeof(done)); Q.push(HeapNode(s,0)); while(!Q.empty()){ HeapNode tNode=Q.top(); Q.pop(); int u=tNode.u; if(done[u]) continue; done[u]=true; for(int i=head[u];i!=-1;i=edges[i].next){ Edge &e=edges[i]; if(d[e.to]>d[u]+e.d){ d[e.to]=d[u]+e.d; p[e.to]=i; Q.push(HeapNode(e.to,d[e.to])); } } } }};Dijkstra sol;int T, n, m;const int maxsize=1000;int cost[maxsize][maxsize][3];int ID(int r,int c,int f){ return f*n*m+r*m+c+1;}int main(){ int d; int cas=0; while(~scanf("%d%d",&n,&m)){ if(n==0&&m==0) break; for(int i=0;i<n;i++) for(int j=0;j<m-1;j++){ scanf("%d",&cost[i][j][0]); } for(int i=0;i<n-1;i++) for(int j=0;j<m;j++){ scanf("%d",&cost[i][j][1]); } for(int i=0;i<n-1;i++) for(int j=0;j<m-1;j++){ scanf("%d",&cost[i][j][2]); } sol.init(2*n*m+2); for(int i=0;i<n-1;i++) for(int j=0;j<m-1;j++){ int id1=ID(i,j,0); if(i<n-1) sol.AddEdge(id1,ID(i+1,j,1),cost[i+1][j][0]); if(j>0) sol.AddEdge(id1,ID(i,j-1,1),cost[i][j][1]); int id2=ID(i,j,1); if(i>0) sol.AddEdge(id2,ID(i-1,j,0),cost[i][j][0]); if(j<m-1) sol.AddEdge(id2,ID(i,j+1,0),cost[i][j+1][1]); sol.AddEdge(id1,id2,cost[i][j][2]); sol.AddEdge(id2,id1,cost[i][j][2]); } for(int i=0;i<n-1;i++){ sol.AddEdge(0,ID(i,0,0),cost[i][0][1]); sol.AddEdge(ID(i,m-2,1),2*n*m+1,cost[i][m-1][1]); } for(int i=0;i<m-1;i++){ sol.AddEdge(0,ID(n-2,i,0),cost[n-1][i][0]); sol.AddEdge(ID(0,i,1),2*n*m+1,cost[0][i][0]); } sol.dijkstra(0); printf("Case %d: Minimum = %d/n",++cas, sol.d[2*n*m+1]); } return 0;}新闻热点
疑难解答
