Blackops

初心易得，始终难守

0%

BZOJ 1001 狼抓兔子（平面图网络流）

发表于 分类于 ， ，

1001: [BeiJing2006]狼抓兔子
Time Limit: 15 Sec Memory Limit: 162 MB
Submit: 26953 Solved: 6872
[Submit][Status][Discuss]

现在小朋友们最喜欢的”喜羊羊与灰太狼”,话说灰太狼抓羊不到，但抓兔子还是比较在行的，

而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：

img

左上角点为(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

Sample Output

14

HINT

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

题目链接：BZOJ 1001

这种平面网格图（或者说按一定规律排列的很多点构成的图），可以建立对偶图，在对偶图上求两个虚拟面的最短路。如果$S-T$有最小割，那么这些割边加上$S-T$这条辅助线会变成一个圈，那么就先新增一条辅助线连接原图的源点$S$和原图的汇点$T$，然后这条辅助线和原图的边将整个大平面分割成了许多小平面，给这些平面标号后再求辅助线分割的小平面到被分割后剩余的大平面的最短路就是要求的答案。~~这种题感觉有一个难点是如何方便快捷地标号，以前想麻烦了就立即放弃构图了，可以发现只要对一些边缘的边特判一下建边，其余的标号都是具有一定规律的

我的建图方式如下：

96sRyQ.png

代码：

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 2000010;
struct edge
{
    int to, nxt, w;
    edge() {}
    edge(int _to, int _nxt, int _w): to(_to), nxt(_nxt), w(_w) {}
} E[N * 4];
int head[N], tot, d[N], vis[N];

void init()
{
    CLR(head, -1);
    tot = 0;
}
void add(int s, int t, int w)
{
    E[tot] = edge(t, head[s], w);
    head[s] = tot++;
    E[tot] = edge(s, head[t], w);
    head[t] = tot++;
    //    printf("[%d  %d]\n", s, t);
}
int spfa(int s, int t)
{
    deque<int>Q;
    CLR(d, 0x3f);
    vis[s] = 1;
    d[s] = 0;
    Q.push_back(s);
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop_front();
        vis[u] = 0;
        for (int i = head[u]; ~i; i = E[i].nxt)
        {
            int v = E[i].to;
            if (d[v] > d[u] + E[i].w)
            {
                d[v] = d[u] + E[i].w;
                if (!vis[v] && d[v] <= d[t])
                {
                    vis[v] = 1;
                    if (!Q.empty() && d[v] < d[Q.front()])
                        Q.push_front(v);
                    else
                        Q.push_back(v);
                }
            }
        }
    }
    return d[t];
}
int main(void)
{
    int n, m, i, j, w;
    while (~scanf("%d%d", &n, &m))
    {
        if (n == 1 && m == 1)
        {
            puts("0");
            continue;
        }
        init();
        int S = 0, T = (n - 1) * (m - 1) * 2 + 1;
        for (j = 1; j < m; ++j)
        {
            scanf("%d", &w);
            add(j, T, w);
        }
        for (i = 2; i <= n - 1; ++i)
        {
            for (j = 1; j < m; ++j)
            {
                scanf("%d", &w);
                add((2 * i - 3) * (m - 1) + j, 2 * (i - 1) * (m - 1) + j, w); //向下
            }
        }
        for (j = 1; j < m; ++j)
        {
            scanf("%d", &w);
            add((2 * n - 3) * (m - 1) + j, S, w);
        }
        for (i = 1; i <= n - 1; ++i)
        {
            for (j = 1; j <= m; ++j)
            {
                scanf("%d", &w);
                if (j == 1)
                {
                    add((2 * i - 1) * (m - 1) + j, S, w);
                }
                else if (j == m)
                {
                    add((2 * (i - 1)) * (m - 1) + j - 1, T, w);
                }
                else
                {
                    add(2 * (i - 1) * (m - 1) + j - 1, 2 * (i - 1) * (m - 1) + j - 1 + m, w);
                }
            }
        }
        for (i = 1; i <= n - 1; ++i)
        {
            for (j = 1; j <= m - 1; ++j)
            {
                scanf("%d", &w);
                add((i - 1) * (m - 1) * 2 + j, (i - 1) * (m - 1) * 2 + j + m - 1, w);
            }
        }
        printf("%d\n", spfa(S, T));
    }
    return 0;
}