BZOJ1001【BJOI2006】狼抓兔子 <网络流>

Posted on Symbols count in article: 923 Reading time ≈ 3 mins.

Problem

【BJOI2006】狼抓兔子

Time  Limit:  15  Sec\mathrm{Time\;Limit:\;15\;Sec}
Memory  Limit:  162  MB\mathrm{Memory\;Limit:\;162\;MB}

Description

现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到，但抓兔子还是比较在行的，
而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对一个网格的地形：
左上角点为(1,1)(1,1),右下角点为(N,M)(N,M).有以下三种类型的道路

  1. (x,y)⇔(x+1,y)(x,y)\Leftrightarrow(x+1,y)
  2. (x,y)⇔(x,y+1)(x,y)\Leftrightarrow(x,y+1)
  3. (x,y)⇔(x+1,y+1)(x,y)\Leftrightarrow(x+1,y+1)

道路上的权值表示这条路上最多能够通过的兔子数，道路是无向的. 左上角和右下角为兔子的两个窝，开始时所有的兔子都聚集在左上角(1,1)(1,1)的窝里，现在它们要跑到右下解(N,M)(N,M)的窝中去，狼王开始伏击些兔子.当然为了保险起见，如果一条道路上最多通过的兔子数为KK，狼王需要安排同样数量的K只狼，才能完全封锁这条道路，你需要帮助狼王安排一个伏击方案，使得在将兔子一网打尽的前提下，参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦.

Input

第一行为N,MN,M.表示网格的大小，N,MN,M均小于等于10001000.
接下来分三部分
第一部分共NN行，每行M−1M-1个数，表示横向道路的权值.
第二部分共N−1N-1行，每行MM个数，表示纵向道路的权值.
第三部分共N−1N-1行，每行M−1M-1个数，表示斜向道路的权值.
输入文件保证不超过10  MB\mathrm{10\;MB}

Output

输出一个整数，表示参与伏击的狼的最小数量.

Sample Input

1
2
3
4
5
6
7
8
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

Sample Output

1
14

HINT

2015.4.162015.4.16新加数据一组，可能会卡掉从前可以过的程序。

标签：网络流

Solution

此题是裸的网络流，看看数据范围，再看看时限，很容易发现直接DinnicDinnic最小割可过。
其实还可以用对偶图上跑最短路做，貌似特判有点多，不太好写，但是要快一些，艹榜可用。

Code

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
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define INF 0x7fffffff
using namespace std;
struct node {int v, c, nxt;} E[12000005];
int n, m, pre[1000005], d[1000005], cnt;
void init() {cnt = 0, memset(pre, -1, sizeof(pre));}
void insert(int u, int v, int c) {
    E[cnt].v = v, E[cnt].c = c, E[cnt].nxt = pre[u], pre[u] = cnt++;
    E[cnt].v = u, E[cnt].c = 0, E[cnt].nxt = pre[v], pre[v] = cnt++;
}
bool BFS() {
    memset(d, -1, sizeof(d));
    queue <int> que;	que.push(1), d[1] = 0;
    while (!que.empty()) {
        int u = que.front();	que.pop();
        for (int i = pre[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c;
            if (~d[v] || !c)	continue;
            d[v] = d[u]+1, que.push(v);
        }
    }
    return d[n*m] != -1;
}
int DFS(int u, int flow) {
    if (u == n*m)	return flow;	int ret = 0;
    for (int i = pre[u]; ~i; i = E[i].nxt) {
        int v = E[i].v, c = E[i].c;
        if (d[u]+1 != d[v] || !c)	continue;
        int tmp = DFS(v, min(flow, c));
        flow -= tmp, ret += tmp, E[i].c -= tmp, E[i^1].c += tmp;
        if (!flow)	break;
    }
    if (!ret)	d[u] = -1;	return ret;
}
int Dinic() {int ret = 0;    while (BFS())	ret += DFS(1, INF);	return ret;}
int main() {
    scanf("%d%d", &n, &m), init();
    for (int i = 1; i <= n; i++)	for (int j = 1, x; j < m; j++)
        scanf("%d", &x), insert(m*(i-1)+j, m*(i-1)+j+1, x), insert(m*(i-1)+j+1, m*(i-1)+j, x);
    for (int i = 1; i < n; i++)	for (int j = 1, x; j <= m; j++)
        scanf("%d", &x), insert(m*(i-1)+j, m*i+j, x), insert(m*i+j, m*(i-1)+j, x);
    for (int i = 1; i < n; i++)	for (int j = 1, x; j < m; j++)
        scanf("%d", &x), insert(m*(i-1)+j, m*i+j+1, x), insert(m*i+j+1, m*(i-1)+j, x);
    printf("%d", Dinic());
    return 0;
}