BZOJ 1001: [BeiJing2006]狼抓兔子（最小割）
Posted On 2018年9月21日
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新加数据一组，可能会卡掉从前可以过的程序。
Source
Solution
裸最小割，有点卡内存。。。
|
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 |
#include <cstdio> #include <cstring> typedef long long ll; const int maxn=1005*1005,inf=1e9; int level[maxn],last[maxn],q[maxn]; int T,mx,mn=1e9; struct mc{int too,nxt;short val;}e[maxn*11]; inline int min(const int a,const int b){return a<b?a:b;} inline int read() { int f=1,k=0;char c=getchar(); while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } int tot=1; inline void ADD(const int a,const int b,const short val) { e[++tot]=(mc){b,last[a],val};last[a]=tot; e[++tot]=(mc){a,last[b],0};last[b]=tot; } inline void add(const int a,const int b,const int val) { ADD(a,b,val);ADD(b,a,val); } inline bool bfs(const int s,const int t) { memset(level,0,sizeof(level)); int front=1,rear=1;q[1]=s;level[s]=1; while (front<=rear) { for (int i=last[q[front]];i;i=e[i].nxt) if (e[i].val>0&&!level[e[i].too]) level[e[i].too]=level[q[front]]+1,q[++rear]=e[i].too; ++front; } return level[t]; } int dfs(const int cur,int flow) { if (cur==T||!flow)return flow; int tmp=0,aw=0; for (int i=last[cur];i;i=e[i].nxt) if (e[i].val>0&&level[e[i].too]==level[cur]+1) { tmp=dfs(e[i].too,min(flow,e[i].val)),aw+=tmp,flow-=tmp,e[i^1].val+=tmp,e[i].val-=tmp; if (flow==0)break; } if (!aw)level[cur]=0; return aw; } signed main() { int n=read(),m=read(),a,b;T=n*m; for (int i=1;i<=n;i++) for (int j=1;j<m;j++) a=(i-1)*m+j,b=a+1,add(a,b,read()); for (int i=1;i<n;i++) for (int j=1;j<=m;j++) a=(i-1)*m+j,b=a+m,add(a,b,read()); for (int i=1;i<n;i++) for (int j=1;j<m;j++) a=(i-1)*m+j,b=a+m+1,add(a,b,read()); ll ans=0; while (bfs(1,n*m))ans+=dfs(1,inf); printf("%lld\n",ans); } |
Subscribe
0 评论