| 题目名称 | 752. [BJOI2006] 狼抓兔子 |
|---|---|
| 输入输出 | bjrabbit.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 3000 ms (3 s) |
| 内存限制 | 162 MiB |
| 测试数据 | 6 |
| 题目来源 |
 Makazeu
于2012-04-07加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：217， 提交：586， 通过率：37.03% | ||||
 Foenix |
100 | 0.074 s | 35.60 MiB | C++ |
 AntiLeaf |
100 | 0.083 s | 133.98 MiB | C++ |
 doriko |
100 | 0.084 s | 154.56 MiB | C++ |
 AAAAAAAAAA |
100 | 0.090 s | 109.06 MiB | C++ |
 _Itachi |
100 | 0.093 s | 94.75 MiB | C++ |
 new ioer |
100 | 0.113 s | 118.54 MiB | C++ |
 _rqy |
100 | 0.113 s | 128.11 MiB | C++ |
 FF_Sky||幻 |
100 | 0.117 s | 53.72 MiB | C++ |
 可以的. |
100 | 0.129 s | 56.74 MiB | C++ |
 一個人的雨 |
100 | 0.167 s | 16.34 MiB | C++ |
| 关于 狼抓兔子 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
先写个暴力练手dinic回头再补qwq
 CSU_Turkey
2017-12-29 14:25
16楼
| ||||
|
用手寫隊列在bzoj上RE了。。。
STL大法好！！！ | ||||
|
为什么我网络流0.191s就过了啊....
 xehoth
2017-05-02 10:36
14楼
| ||||
|
强行最大流卡时A
改成最短路后，感觉代码整齐些是好的。。 BZOJ上不断挑战数组大小，在RE和M的边界上挣扎了8次才过。。 | ||||
|
以撒在这边可过,隔壁BZOJ炸内存
 YGOI_真神名曰驴蛋蛋
2016-10-16 06:03
12楼
| ||||
|
BZOJ上内存是162MB
| ||||
|
为什么spfa都过了。。。
一开始是超时的。。后来我想“特判”（dabiao)一下，结果就过了。。。 | ||||
|
膜拜最大流完爆的常数帝......
一個人的雨
2015-08-08 21:52
9楼
| ||||
|
对偶图是什么鬼，可以吃吗？
红果果的最大流，常数大如狗......只好特判了，罪过，罪过 | ||||
kZime
神利·代目
asddddd
HouJikanDescription Source: Beijing2006 [BJOI2006]
八中OJ上本题链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1001
现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到，但抓兔子还是比较在行的，而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：
左上角点为(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