BZOJ 1001: [BeiJing2006]狼抓兔子 – [最小割/对偶图最短路]


题目传送门(BZOJ)
>原文链接<

题解 :

这篇文章有一个假标题

题意就是求一个最小割, 那我们就求一个最小割咯.

细心的你一定发现这个东西用dinic跑不下来, 然后我们需要转成对偶图最短路.

但是不细心的我并没有看数据范围, 直接连边跑dinic就过了

你看, 非常好写 (老脸一红

代码 :

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N =1e6;
const int inf = 0x3f3f3f3f;
#define P(i, j) (((i)-1)*m+(j))
int head[N+10], to[N*6+10], val[N*6+10], next[N*6+10];
int cnt = 1;
int dep[N+10];
int n, m, s, t;
void add_edge(int a, int b, int c) {
    to[++cnt] = b; next[cnt] = head[a]; head[a] = cnt; val[cnt] = c;
    to[++cnt] = a; next[cnt] = head[b]; head[b] = cnt; val[cnt] = c;
}
queueq;
bool bfs() {
    memset(dep, 0, sizeof(dep));
    while(!q.empty())q.pop();
    q.push(s);
    dep[s]=1;
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=next[i]) {
            if(!dep[to[i]]&&val[i]) {
                dep[to[i]]=dep[u]+1;
                if(to[i]==t)return 1;
                q.push(to[i]);
            }
        }
    }
    return 0;
}
int dfs(int p, int mf) {
    int nf = 0;
    if(p==t)return mf;
    for(int i = head[p]; i; i = next[i] ) {
        if(dep[to[i]]==dep[p]+1&&val[i]) {
            int tmp=dfs(to[i], min(mf-nf, val[i]));
            if(!tmp)dep[to[i]]=0;
            nf+=tmp;
            val[i]-=tmp;
            val[i^1]+=tmp;
            if(nf==mf)break;
        }
    }
    return nf;
}
void dinic() {
    int ans=0, tmp=0;
    while(bfs()) {
        while(tmp=dfs(s, inf)) 
            ans+=tmp;
    }
    printf("%d\n", ans);
}
int main() {
    scanf("%d%d", &n, &m);
    s = n*m+1, t = n*m+2;
    for(int i = 1; i <= n; i ++ ) for(int j = 1; j < m; j ++ ) {
        int x; scanf("%d", &x);
        add_edge(P(i, j), P(i, j+1), x);
    }
    for(int i = 1; i < n; i ++ ) for(int j = 1; j <= m; j ++ ) {
        int x; scanf("%d", &x);
        add_edge(P(i, j), P(i+1, j), x);
    }
    for(int i = 1; i < n; i ++ ) for(int j = 1; j < m; j ++ )  {
        int x; scanf("%d", &x);
        add_edge(P(i, j), P(i+1, j+1), x);
    }
    add_edge(s, 1, inf);
    add_edge(P(n, m), t, inf);
    dinic();
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注