3
19
2019
1

BZOJ1001 -- [BeiJing2006]狼抓兔子

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

Sample Output

14

HINT

 

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

 

Source

题解:

我们很简单的可以想到这道题是最小割问题,那么最小割=最大流。

 

#include <stdio.h>
#include <memory.h>
#define inf 1000000001
 
inline int min(register int a , register int b) { return a < b ? a : b ; }
 
#define getch() getchar()
inline int F() { register int aa , bb , ch;
    while(ch = getch() , (ch<'0'||ch>'9') && ch != '-'); ch == '-' ? aa=bb=0 : (aa=ch-'0',bb=1);
    while(ch = getch() , ch>='0'&&ch<='9') aa = aa*10 + ch-'0'; return bb ? aa : -aa;
}
 
const int Maxn = 1000010;
const int Maxm = 6000010;
 
#define R register 
int to[Maxm] , next[Maxm] , g[Maxn] , w[Maxm] , ecnt = 1;
int n , m , S , T , h , t , ans = 0;
int dep[Maxn] , q[Maxm];
 
inline void ins(int a , int b , int c) {
    to[++ecnt] = b; next[ecnt] = g[a]; g[a] = ecnt; w[ecnt] = c;
    to[++ecnt] = a; next[ecnt] = g[b]; g[b] = ecnt; w[ecnt] = c;
}
 
inline bool bfs() {
    memset(dep,-1,sizeof(dep));dep[T] = 0;
    q[h = t = 1] = T;
    while(h <= t) {
        R int now = q[h++];
        for(R int i=g[now]; i; i=next[i]) {
            if(w[i^1] && dep[to[i]] == -1) {
                dep[to[i]] = dep[now] + 1;
                q[++t] = to[i];
            }
        }
    }
    return dep[S] != -1;
}
 
inline int dfs(int x , int lim) {
    if(x == T) return lim;
    R int v,used = 0;
    for(R int i=g[x]; i; i=next[i]) {
        if(w[i] && (dep[to[i]]+1 == dep[x])) {
            v = dfs(to[i] , min(lim-used , w[i]));
            w[i] -= v;
            w[i^1] += v;
            used += v;
            if(used == lim) return lim;
        }
    }
    if (!used) dep[x]=-1;
    return used;
}
 
void dinic() { while(bfs()) { ans += dfs(S,inf); } }
 
int main() {
    R int tmp;
    n = F(); m = F();
    S = 1 ; T = n*m;
    for(R int i=0; i<n; ++i)
        for(R int j=1; j<m; ++j) {
            tmp = F();
            ins(i*m+j,i*m+j+1,tmp);
        }
    for(R int i=0; i<n-1; ++i)
        for(R int j=1; j<=m; ++j) {
            tmp = F();
            ins(i*m+j,(i+1)*m+j,tmp);
        }
    for(R int i=0; i<n-1; ++i)
        for(R int j=1; j<m; ++j) {
            tmp = F();
            ins(i*m+j,(i+1)*m+j+1,tmp);
        }
    dinic();
    printf("%d\n",ans );
}

但是这道题的数据范围显然是不支持n3的,只有写的优秀的暴力网络流能A(虽然我写的这么弱还是A了。。)

所以我们考虑到,这张图是一个平面图,我们可以把它变成对偶图。我们考虑把每一个“三角形当作一个点”,把整张图分为

Category: BZOJ | Tags: SPFA 网络流 最短路 最小割 平面图转对偶图 | Read Count: 305
Avatar_small
Comprar seguidores 说:
2020年9月02日 20:29

Olá, acho a leitura deste artigo uma alegria. É extremamente útil e interessante e estou ansioso para ler mais sobre o seu trabalho.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com