【HDU - 3870】Catch the Theves（平面图转对偶图最短路，网络流最小割）

题干：

A group of thieves is approaching a museum in the country of zjsxzy,now they are in city A,and the museum is in city B,where keeps many broken legs of zjsxzy.Luckily,GW learned the conspiracy when he is watching stars and told it to zjsxzy. 
Zjsxzy decided to caught these thieves,and he let the police to do this,the police try to catch them on their way from A to B. Although the thieves might travel this way by more than one group, zjsxzy's excellent police has already gather the statistics that the cost needed on each road to guard it. 
Now ,zjsxzy's conutry can be described as a N*N matrix A,Aij indicates the city(i,j) have bidirectionals road to city(i+1,j) and city(i,j+1),gurad anyone of them costs Aij. 
Now give you the map,help zjsxzy to calculate the minimium cost.We assume thieves may travel in any way,and we will catch all passing thieves on a road if we guard it. 

Input

The first line is an integer T,followed by T test cases. 
In each test case,the first line contains a number N(1<N<=400). 
The following N lines,each line is N numbers,the jth number of the ith line is Aij. 
The city A is always located on (1,1) and the city B is always located on (n,n). 
Of course,the city (i,j) at the last row or last line won't have road to (i,j+1) or (i+1,j). 

Output

For each case,print a line with a number indicating the minimium cost to arrest all thieves.

Sample Input

1 3 10 5 5 6 6 20 4 7 9

Sample Output

18

Hint

The map is like this:

题目大意：

有一个n*n个点的格子。输入n*n条边，每个边权代表(i,j) -> (i,j+1) 和 (i,j) -> (i+1,j)这两条边的边权。求左上角到右下角的最小割、

解题报告：

  直接转对偶图跑最短路。但是建图的时候细节要注意一下。别建多了边，写错了符号啥的。

AC代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 4e5 + 5; const int INF = 0x3f3f3f3f; struct Edge {int u,v,w;int ne; } e[MAX<<2]; int n; int head[MAX],tot; void add(int u,int v,int w) {//加双向边 e[++tot].v = v; e[tot].w = w; e[tot].ne = head[u]; head[u] = tot;e[++tot].v = u; e[tot].w = w; e[tot].ne = head[v]; head[v] = tot; } int ID(int x,int y) {return (x-1)*n + y; } int dis[MAX],vis[MAX]; struct Point {int pos,dis;Point(int pos=0,int dis=0):pos(pos),dis(dis){}bool operator < (const Point & b) const {return dis > b.dis;} }; int Dij(int st,int ed) {priority_queue<Point> pq;pq.push(Point(st,0));dis[st]=0;while(pq.size()) {Point cur = pq.top();pq.pop();if(vis[cur.pos]) continue;vis[cur.pos] = 1;for(int i = head[cur.pos]; ~i; i = e[i].ne) {int v = e[i].v;if(dis[v] > dis[cur.pos] + e[i].w) {dis[v] = dis[cur.pos] + e[i].w;pq.push(Point(v,dis[v]));}} }return dis[ed]; } int main() {int t;cin>>t;while(t--) {tot=0;scanf("%d",&n);for(int i = 0; i<=n*n + 2; i++) head[i] = -1,dis[i] = INF,vis[i] = 0;int st = n*n+1,ed=n*n+2;for(int x,i = 1; i<=n; i++) {for(int j = 1; j<=n; j++) {scanf("%d",&x);if( (i==1&&j!=n)|| (j==n&&i!=n) ) add(ID(i,j-(j==n)),ed,x);//和汇点 if( (i==n&&j!=n)|| (j==1&&i!=n) ) add(ID(i-(i==n),j),st,x);//和起点 if(i != 1 && i != n && j != n) add(ID(i-1,j),ID(i,j),x);//水平行之间if(j != 1 && j != n && i != n) add(ID(i,j-1),ID(i,j),x);//竖直列之间 }}printf("%d\n",Dij(st,ed)); }return 0 ; }

总结：

  建图的过程中虽然非常的显而易见，但是还是出现了细节问题。比如刚开始直接写的和源点和汇点的连边，直接就是i==1||j==n代表和汇点相连，显然这样写会有重边，不光如此，第一行最右侧那一条边在连边的时候，要注意是ID(i,j-1)和ed相连。

还有判断水平边(以水平边为例)的时候，不仅要有i!=1&&i!=n，还要有j!=n这一个条件！总之别落下了判断条件就行。

总结

以上是生活随笔为你收集整理的【HDU - 3870】Catch the Theves（平面图转对偶图最短路，网络流最小割）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。