3
19
2019
2

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: 473
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.

Avatar_small
AP 1st Inter Botany 说:
2022年9月08日 19:30

In intermediate education, Botany is a very important subject for science group students for part-1 and part-2 first and the second year of junior and senior intermediate students, and the BIEAP has conducted the General Science examination tests including botany subject, download AP inter Botany Model Paper 2023 AP 1st Inter Botany Model Paper Pdf with solutions for all 1st and 2nd-year students for paper-1 and paper-2 exams 2023.


登录 *


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