Description
现在小朋友们最喜欢的”喜羊羊与灰太狼”,话说灰太狼抓羊不到，但抓兔子还是比较在行的，
而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：
左上角点为(1,1),右下角点为(N,M)(上图中N=4,M=5).有以下三种类型的道路
1:(x,y)<==>(x+1,y)
2:(x,y)<==>(x,y+1)
3:(x,y)<==>(x+1,y+1)
道路上的权值表示这条路上最多能够通过的兔子数，道路是无向的. 左上角和右下角为兔子的两个窝，
开始时所有的兔子都聚集在左上角(1,1)的窝里，现在它们要跑到右下解(N,M)的窝中去，狼王开始伏击
这些兔子.当然为了保险起见，如果一条道路上最多通过的兔子数为K，狼王需要安排同样数量的K只狼，
才能完全封锁这条道路，你需要帮助狼王安排一个伏击方案，使得在将兔子一网打尽的前提下，参与的
狼的数量要最小。因为狼还要去找喜羊羊麻烦.
Input
第一行为N,M.表示网格的大小，N,M均小于等于1000.
接下来分三部分
第一部分共N行，每行M-1个数，表示横向道路的权值.
第二部分共N-1行，每行M个数，表示纵向道路的权值.
第三部分共N-1行，每行M-1个数，表示斜向道路的权值.
输入文件保证不超过10M
Output
输出一个整数，表示参与伏击的狼的最小数量.
Sample Input
3 4
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6
Sample Output
14
HINT
2015.4.16新加数据一组，可能会卡掉从前可以过的程序。
最小割转最短路。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
#include<iostream> #include<cstdio> #include<queue> #include<algorithm> using namespace std; const int N=2000000,M=6000000; int n,m,X,tot,Next[M],head[N],tree[M],val[M],dis[N]; bool visit[N]; struct node{int p,q;}t; struct cmp { bool operator()(node a,node b) { return a.q>b.q; } }; priority_queue<node,vector<node>,cmp> Q; void add(int x,int y,int z) { Next[++tot]=head[x];head[x]=tot;tree[tot]=y;val[tot]=z; Next[++tot]=head[y];head[y]=tot;tree[tot]=x;val[tot]=z; } int Dijstra(int S,int T) { for (int i=1;i<=X+2;i++) dis[i]=1<<29,visit[i]=false; t.p=S;t.q=0; dis[S]=0; Q.push(t); while (!Q.empty()) { t=Q.top(); Q.pop(); int u=t.p; visit[u]=true; for (int i=head[u];i;i=Next[i]) { int v=tree[i]; if (dis[v]>dis[u]+val[i]) { dis[v]=dis[u]+val[i]; t.p=v;t.q=dis[v]; Q.push(t); } } } return dis[T]; } int main() { scanf("%d%d",&n,&m); if (n==1||m==1) { if (n==1&&m==1) {puts("0");return 0;} int ans=1<<29,x; for (int i=1;i<=max(n,m)-1;i++) { scanf("%d",&x);ans=min(ans,x);} printf("%d\n",ans); return 0; } X=(n-1)*(m-1)*2; tot=0; for (int i=1;i<=n;i++) for (int j=1;j<m;j++) { int x; scanf("%d",&x); if (i==1) add(X+1,j,x); if (i==n) add(X+2,j+(i-2)*(m-1)*2+(m-1),x); if (i!=1&&i!=n) add(j+(i-2)*(m-1)*2+(m-1),j+(i-1)*(m-1)*2,x); } for (int i=1;i<n;i++) for (int j=1;j<=m;j++) { int x; scanf("%d",&x); if (j==1) add(X+2,j+(i-1)*(m-1)*2+(m-1),x); if (j==m) add(X+1,j+(i-1)*(m-1)*2-1,x); if (j!=1&&j!=m) add(j+(i-1)*(m-1)*2+(m-1),j+(i-1)*(m-1)*2-1,x); } for (int i=1;i<n;i++) for (int j=1;j<m;j++) { int x; scanf("%d",&x); add(j+(i-1)*(m-1)*2,j+(i-1)*(m-1)*2+(m-1),x); } printf("%d\n",Dijstra(X+1,X+2)); return 0; } |
转化方法
https://wenku.baidu.com/view/b31cc3d6c1c708a1284a447e.html
司机厉害啊上各种论文↑
终于找到你大佬的证据了