bzoj1001 [BeiJing2006]狼抓兔子 對偶圖

Description

給定一個網格圖和邊權求(1,1)到(n,m)的最小割

Solution

顯然直接最大流是會T的，這裡需要模型轉換一下

詳見這篇論文

轉成對偶圖跑spfa即可

注意隻有一行和隻有一列的情況要特判一下

Code

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define fill(x,t) memset(x,t,sizeof(x))

const int INF=;
const int N=;
const int E=;

struct edge {int y,w,next;} e[E];

std:: queue <int> que;

int dis[N];
int ls[N],edCnt;

bool vis[N];

void add_edge(int x,int y,int w) {
    e[++edCnt]=(edge) {y,w,ls[x]}; ls[x]=edCnt;
    e[++edCnt]=(edge) {x,w,ls[y]}; ls[y]=edCnt;
}

void spfa(int st) {
    fill(dis,); dis[st]=;
    que.push(st);
    while (!que.empty()) {
        int now=que.front(); que.pop();
        for (int i=ls[now];i;i=e[i].next) {
            if (dis[now]+e[i].w>=dis[e[i].y]) continue;
            dis[e[i].y]=dis[now]+e[i].w;
            if (vis[e[i].y]) continue;
            vis[e[i].y]=;
            que.push(e[i].y);
        }
        vis[now]=;
    }
}

void build(int n,int m) {
    int s=,t=(n-)*(m-)*+;
    rep(j,,m-) {
        int w; scanf("%d",&w);
        add_edge(j*,t,w);
    }
    rep(i,,n-) rep(j,,m-) {
        int w; scanf("%d",&w);
        add_edge(*((i-)*(m-)+j),*((i-)*(m-)+j)-,w);
    }
    rep(j,,m-) {
        int w; scanf("%d",&w);
        add_edge(s,*((n-)*(m-)+j)-,w);
    }
    rep(i,,n-) {
        int w; scanf("%d",&w);
        add_edge(s,*((i-)*(m-))+,w);
        rep(j,,m-) {
            scanf("%d",&w);
            add_edge(*((i-)*(m-)+j)-,*((i-)*(m-)+j-),w);
        }
        scanf("%d",&w);
        add_edge(*((i-)*(m-)+m-),t,w);
    }
    rep(i,,n-) rep(j,,m-) {
        int w; scanf("%d",&w);
        add_edge(*((i-)*(m-)+j)-,*((i-)*(m-)+j),w);
    }
}

int main(void) {
    int n,m; scanf("%d%d",&n,&m);
    if (n==&&m==) {
        puts("0");
        return ;
    }
    int ans=INF;
    if (n==) {
        rep(i,,m-) {
            int x; scanf("%d",&x);
            ans=std:: min(ans,x);
        }
        printf("%d\n", ans);
        return ;
    }
    if (m==) {
        rep(i,,n-) {
            int x; scanf("%d",&x);
            ans=std:: min(ans,x);
        }
        printf("%d\n", ans);
        return ;
    }
    build(n,m);
    spfa();
    printf("%d\n", dis[(n-)*(m-)*+]);
    return ;
}