洛咕 P4474 王者之剑

宝石只能在偶数秒取到，假设有一个宝石在奇数秒取到了，那么上一秒是偶数秒，在上一秒的时候这里的宝石就没了。

相邻的两个宝石不能同时取，很显然，先取一块，那么这是偶数秒，取完了这一块之后相邻的都没了。

只要不取相邻两个宝石，一定能构造出一种合法的方案（为什么？看胡伯涛的论文

所以答案就是二分图最小点权覆盖

#include<bits/stdc++.h>

#define il inline

#define vd void

typedef long long ll;

il int gi(){

    int x=0,f=1;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')f=-1;

        ch=getchar();

    }

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

int num[101][101],fir[10010],dep[10010],head[10010],dis[1000010],nxt[1000010],w[1000010],id=1,S,T;

il vd link(int a,int b,int c){

    nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=c;

    nxt[++id]=fir[b],fir[b]=id,dis[id]=a,w[id]=0;

}

il bool BFS(){

    memset(dep,0,sizeof dep);

    static int que[10010],hd,tl;

    hd=tl=0,que[tl++]=S;dep[S]=1;

    while(hd^tl){

        int x=que[hd++];

        for(int i=fir[x];i;i=nxt[i])

            if(w[i]&&!dep[dis[i]])

                dep[dis[i]]=dep[x]+1,que[tl++]=dis[i];

    }

    return dep[T];

}

il int Dinic(int x,int maxflow){

    if(x==T)return maxflow;

    int ret=0;

    for(int&i=head[x];i;i=nxt[i])

        if(w[i]&&dep[dis[i]]==dep[x]+1){

            int d=Dinic(dis[i],std::min(maxflow-ret,w[i]));

            w[i]-=d,w[i^1]+=d,ret+=d;

            if(ret==maxflow)break;

        }

    return ret;

}

int main(){

#ifndef ONLINE_JUDGE

    freopen("4474.in","r",stdin);

    freopen("4474.out","w",stdout);

#endif

    int n=gi(),m=gi(),ans=0,W,cnt=0;

    S=++cnt,T=++cnt;

    for(int i=1;i<=n;++i)

        for(int j=1;j<=m;++j){

            W=gi();ans+=W;

            num[i][j]=++cnt;

            if((i+j)&1)link(S,num[i][j],W);

            else link(num[i][j],T,W);

        }

    for(int i=1;i<=n;++i)

        for(int j=1;j<=m;++j)

            if((i+j)&1){

                if(i<n)link(num[i][j],num[i+1][j],1e9);

                if(j<m)link(num[i][j],num[i][j+1],1e9);

                if(i>1)link(num[i][j],num[i-1][j],1e9);

                if(j>1)link(num[i][j],num[i][j-1],1e9);

            }

    while(BFS())memcpy(head,fir,sizeof head),ans-=Dinic(S,1e9);

    printf("%d\n",ans);

    return 0;

}

巴特西

洛咕 P4474 王者之剑

最新文章

热门文章