BZOJ 1412: [ZJOI2009]狼和羊的故事 – [网络最小割]


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

题解 :

看上去就是一道最小割, 做起来也是一道最小割

我们只需要考虑如何把羊和狼隔开就行了不是吗

对于羊的领地, 从S到其连一条val = INF的边, 因为它不能被割掉

同理, 从狼的领地向T连一条val = INF的边.

对于建篱笆, 我们从每个点向四周连一条权值为1的边, 代表可以通过,

而求一个最小割, 就可以通过割掉权值为1的边实现隔开狼和羊

大功告成! 我甚至懒得再写一次Dinic.

代码 :

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N =1e5+10;
const int inf = 0x3f3f3f3f;
#define P(i,j) ((i-1)*m+j)
int head[N+10], to[N*6+10], val[N*6+10], nxt[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; nxt[cnt] = head[a]; head[a] = cnt; val[cnt] = c;
    to[++cnt] = a; nxt[cnt] = head[b]; head[b] = cnt; val[cnt] = 0;
}
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=nxt[i]) {
            if(!dep[to[i]]&&val[i]) {
                dep[to[i]]=dep[u]+1;
                q.push(to[i]);
            }
        }
    }
    return dep[t]!=0;
}
int dfs(int p,int mf) {
    int nf=0;
    if(p==t)return mf;
    for(int i=head[p];i;i=nxt[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;
    while(bfs()) {
        ans+=dfs(s,inf);
    }
    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);
        if(x==1) add_edge(s, P(i,j), inf);
        else if(x==2) add_edge(P(i,j), t, inf);
        if(i>1) add_edge(P(i,j),P(i-1,j),1);
        if(i1) add_edge(P(i,j),P(i,j-1),1);
        if(j

发表评论

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