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新加数据一组,可能会卡掉从前可以过的程序。
题解
这道题一眼看到就觉得是网络流
也可以用最短路来做
这里介绍一下网络流的做法
我们可以把一对(x,y)转化成一个值(n和m都小于等于1000,所以(n,m)最大也就1,000,000)
加边,进行网络流
但是网络流我以前只会O(n^2*m) 的,看数据感觉要超时
后来发现当dfs找答案的时候可以优化一下(具体可以看一下我的上一篇博客)
所以这样时间复杂度立刻就降下来了
- #include < bits / stdc++.h > #define MAX 1e9#define NM 1000005 using namespace std;
- int n,
- m,
- val,
- tot,
- ans,
- dis;
- int head[NM],
- level[NM],
- q[NM];
- struct node {
- int next,
- to,
- dis;
- }
- E[6 * NM];
- void add(int x, int y, int z) {
- tot++;
- E[tot].next = head[x];
- head[x] = tot;
- E[tot].to = y;
- E[tot].dis = z;
- tot++;
- E[tot].next = head[y];
- head[y] = tot;
- E[tot].to = x;
- E[tot].dis = z;
- }
- void pre() {
- for (int i = 1; i <= n; i++) for (int j = 1; j < m; j++) {
- scanf("%d", &val);
- add((i - 1) * m + j, (i - 1) * m + j + 1, val);
- }
- for (int i = 1; i < n; i++) for (int j = 1; j <= m; j++) {
- scanf("%d", &val);
- add((i - 1) * m + j, i * m + j, val);
- }
- for (int i = 1; i < n; i++) for (int j = 1; j < m; j++) {
- scanf("%d", &val);
- add((i - 1) * m + j, i * m + j + 1, val);
- }
- }
- bool bfs() {
- memset(level, 0, sizeof(level));
- level[1] = 1;
- int t = 1,
- w = 1;
- q[1] = 1;
- while (t <= w) {
- int k = q[t];
- for (int i = head[k]; i != -1; i = E[i].next) {
- int y = E[i].to;
- if (E[i].dis && !level[y]) {
- level[y] = level[k] + 1;
- q[++w] = y;
- }
- }
- t++;
- }
- return level[n * m] != 0;
- }
- int dfs(int s, int maxf) {
- if (s == n * m) return maxf;
- int ret = 0;
- for (int i = head[s]; i != -1; i = E[i].next) {
- int y = E[i].to;
- dis = E[i].dis;
- if (dis && level[s] + 1 == level[y]) {
- int Min = min(maxf - ret, dis);
- dis = dfs(y, Min);
- E[i].dis -= dis;
- E[i ^ 1].dis += dis;
- ret += dis;
- if (ret == maxf) return ret;
- }
- }
- if (!ret) level[s] = 0;
- return ret;
- }
- void Dinic() {
- ans = 0;
- while (bfs()) ans += dfs(1, MAX);
- printf("%d\n", ans);
- }
- int main() {
- scanf("%d%d", &n, &m);
- memset(head, -1, sizeof(head));
- pre();
- Dinic();
- return 0;
- }
posted @2017-09-30 23:36 I__am阅读(...) 评论(...)编辑 收藏