题意：动物逃跑，从左上跑到右下角，逃跑的路径是一个grid的边，现在动物园的工作人员要去拦截。input给出了grid每条路径拦截所需要的cost，题目要求拦截成功最小的成本。
经典的最小割问题，但是400*400个点太大了，所以不能直接这么做
lrj给出的方法是动物要从左上跑到右下，所有我们考虑怎么摆障碍物就可以了，思考可以知道，只要做左/下->右/上的连续拦截边，就可以将所有可行路径分割开。如下图(偷了别人博客的图。。。)
这张图其实是hdu3870的图，题意差不多，但是没有斜边，所以少了两倍的点，建图也简单的多。从左/下到右/上的拦截边可以这样考虑，增加s源点，ed终点，最在要求拦截的成功的最小成本就是从s到t可最短可行边，dij模板套一下就可以了
难点在思考和建图，边转化为点，重新建图刚开始看还是挺毁我三观的
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <stack> #include <string> #include <queue> #include <vector> #include <algorithm> #include <ctime> using namespace std; #define EdsonLin #ifdef EdsonLin #define debug(...) fprintf(stderr,__VA_ARGS__) #else #define debug(...) #endif //EdsonLin typedef long long ll; typedef double db; const int inf = 0x3f3f3f; const int MAXN = 1e3; const int MAXNN = 2e6+100; //const int MAXM = 1e6; //const int MAXM = 3e4+100; const int MOD = 1000000007; const db eps = 1e-3; #define PB push_back #define UP(i) ((i)<<1) #define DOWN(i) ((UP(i))-1) struct dij{ int n,m; int first[MAXNN]; struct edge{ int st,to,next,dist; }; vector<edge>e; int top; int d[MAXNN]; //s到各节点的距离 int done[MAXNN]; //是否已经被永久标记 int p[MAXNN]; //记录上一条边 struct heapnode{ int st; int dist; bool operator < (const heapnode& rhs) const { return dist>rhs.dist; } }; void init(int n){ this->n = n; memset(first,-1,sizeof(first)); top = 0; e.clear(); } void addedge(int u,int v,int dist){ /*e[top].st = u; e[top].to = v; e[top].dist = dist; e[top].next = first[u]; first[u] = top++;*/ edge a; a.st = u; a.to = v; a.dist = dist; a.next = first[u]; e.PB(a); first[u] = top++; //cout<<first[u]<<endl; //cout<<top<<endl; } void pqdij(int s){ priority_queue<heapnode>Q; heapnode a; for(int i=0;i<n;i++) d[i] = inf; d[s] = 0; memset(done,0,sizeof(done)); a.dist = 0; a.st = s; Q.push(a); while(!Q.empty()){ heapnode x = Q.top(); Q.pop(); int u = x.st; if(done[u])continue; done[u] = 1; for(int i=first[u];i!=-1;i=e[i].next){ if(d[e[i].to]>d[u]+e[i].dist){ d[e[i].to] = d[u] + e[i].dist; p[e[i].to] = i; a.dist = d[e[i].to]; a.st = e[i].to; Q.push(a); } } } } }solver; int hor[MAXN][MAXN],vec[MAXN][MAXN],dia[MAXN][MAXN]; int readint(){int x;scanf("%d",&x);return x;} int main() { #ifdef EdsonLin //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); int _time_ed = clock(); #endif //EdsonLin int mc=0,n,m; while(scanf("%d%d",&n,&m)&&n){ for(int i=1;i<=n;i++){ for(int j=1;j<m;j++) hor[i][j] = readint(); } for(int i=1;i<n;i++){ for(int j=1;j<=m;j++) vec[i][j] = readint(); } for(int i=1;i<n;i++){ for(int j=1;j<m;j++) dia[i][j] = readint(); } int st=0,ed = (n-1)*(m-1)*2+1; solver.init(ed+1); for(int i=1;i<n;i++){ for(int j=1;j<m;j++){ if(i==1){ solver.addedge(2*(i-1)*(m-1)+UP(j),ed,hor[i][j]); solver.addedge(ed,2*(i-1)*(m-1)+UP(j),hor[i][j]); } if(i==n-1){ solver.addedge(st,2*(i-1)*(m-1)+DOWN(j),hor[i+1][j]); solver.addedge(2*(i-1)*(m-1)+DOWN(j),st,hor[i+1][j]); } if(i!=n-1){ solver.addedge(2*(i-1)*(m-1)+DOWN(j),2*(i)*(m-1)+UP(j),hor[i+1][j]); solver.addedge(2*i*(m-1)+UP(j),2*(i-1)*(m-1)+DOWN(j),hor[i+1][j]); } if(j==1){ solver.addedge(st,2*(i-1)*(m-1)+DOWN(j),vec[i][j]); solver.addedge(2*(i-1)*(m-1)+DOWN(j),st,vec[i][j]); } if(j!=m-1){ solver.addedge(2*(i-1)*(m-1)+DOWN(j),2*(i-1)*(m-1)+UP(j),dia[i][j]); solver.addedge(2*(i-1)*(m-1)+UP(j),2*(i-1)*(m-1)+DOWN(j),dia[i][j]); solver.addedge(2*(i-1)*(m-1)+UP(j),2*(i-1)*(m-1)+DOWN(j+1),vec[i][j+1]); solver.addedge(2*(i-1)*(m-1)+DOWN(j+1),2*(i-1)*(m-1)+UP(j),vec[i][j+1]); } if(j==m-1){ solver.addedge(2*(i-1)*(m-1)+DOWN(j),2*(i-1)*(m-1)+UP(j),dia[i][j]); solver.addedge(2*(i-1)*(m-1)+UP(j),2*(i-1)*(m-1)+DOWN(j),dia[i][j]); solver.addedge(2*(i-1)*(m-1)+UP(j),ed,vec[i][j+1]); solver.addedge(ed,2*(i-1)*(m-1)+UP(j),vec[i][j+1]); } } } solver.pqdij(st); printf("Case %d: Minimum = %d ",++mc,solver.d[ed]); } #ifdef EdsonLin debug("time: %d ",int(clock()-_time_ed)); #endif //EdsonLin // cout << "Hello world!" << endl; return 0; }