1001: [BeiJing2006]狼抓兔子
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
---------------------------------------------->_<------------------------------------------
经典最小割问题
然而点数太多会T
发现本题是构建在平面图上
所以可以将原图转换成对偶图上跑最短路就是原图的最小割
#include<iostream> #include<stdlib.h> #include<stdio.h> #include<math.h> #include<algorithm> #include<vector> #include<queue> using namespace std; int n,m; vector<int> f[2000051]; vector<int> val[2000051]; int dis[2000051]; bool b[2000051]; struct squ { int dis,p; squ(){} squ(int a,int b){dis=a;p=b;} }; int INF=2100000000; bool operator <(squ a,squ b){return a.dis>b.dis;} priority_queue<squ> que; void init() { scanf("%d%d",&n,&m); if(n==1||m==1) { if(n>m)swap(n,m); int ans=INF; for(int i=1;i<m;i++) { int c; scanf("%d",&c); if(ans>c)ans=c; } if(ans==INF) cout<<0<<endl; else cout<<ans<<endl; } else { int ins=(n-1)*(m-1); int fin=2*ins+1; //上点i*m+j 下点 i*m+j+ins; //起点 0 终点 2*ins+1 for(int i=0;i<n;i++) for(int j=1;j<m;j++) { int c; scanf("%d",&c); if(i==0) { int x=i*(m-1)+j; f[0].push_back(x); f[x].push_back(0); val[0].push_back(c); val[x].push_back(c); } if(i>0&&i<n-1) { int x=(i-1)*(m-1)+j+ins,y=i*(m-1)+j; f[y].push_back(x); f[x].push_back(y); val[x].push_back(c); val[y].push_back(c); } if(i==n-1) { int x=(i-1)*(m-1)+j+ins; f[x].push_back(fin); f[fin].push_back(x); val[fin].push_back(c); val[x].push_back(c); } } for(int i=0;i<n-1;i++) for(int j=1;j<=m;j++) { int c; scanf("%d",&c); if(j==1) { int x=i*(m-1)+j+ins; f[x].push_back(fin); f[fin].push_back(x); val[fin].push_back(c); val[x].push_back(c); } if(j>1&&j<m) { int x=i*(m-1)+j-1,y=i*(m-1)+j+ins; f[y].push_back(x); f[x].push_back(y); val[y].push_back(c); val[x].push_back(c); } if(j==m) { int x=i*(m-1)+j-1; f[x].push_back(0); f[0].push_back(x); val[0].push_back(c); val[x].push_back(c); } } for(int i=0;i<n-1;i++) for(int j=1;j<m;j++) { int c; scanf("%d",&c); int x=i*(m-1)+j,y=i*(m-1)+j+ins; f[y].push_back(x); f[x].push_back(y); val[y].push_back(c); val[x].push_back(c); } que.push(squ(0,0)); for(int i=1;i<=fin;i++) dis[i]=INF; dis[0]=0; for(;!que.empty();) { squ x=que.top(); que.pop(); int d=x.dis; if(x.p==fin)break; if(b[x.p])continue; b[x.p]=1; for(int i=0;i<f[x.p].size();i++) { int next=f[x.p][i]; if(!b[next]&&d+val[x.p][i]<dis[next]) {dis[next]=d+val[x.p][i]; que.push(squ(dis[next],next));} } } cout<<dis[fin]<<endl; } } int main() { init(); return 0; }