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

Problem

【BJOI2006】狼抓兔子

Description

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

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

Input

第一行为.表示网格的大小，均小于等于.
接下来分三部分
第一部分共行，每行个数，表示横向道路的权值.
第二部分共行，每行个数，表示纵向道路的权值.
第三部分共行，每行个数，表示斜向道路的权值.
输入文件保证不超过

Output

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

Sample Input

Sample Output

HINT

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

标签：网络流

Solution

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

Code

#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;
}