题目分析

先将网格图红白染色(你问为什么不是黑白?因为我在草稿纸上画图时发现把黑色格子改成红色是不可能的……)。

然后将与蓝色线相邻的红色格子改成黑色,相邻的白色格子改成蓝色。

大概长这样(灵魂画手 litble 再现江湖!)

灵魂画手litble

这样你会发现:

1. 整张图黑格子与红格不相邻,蓝格子和白格子不相邻。

2. 任何一个特殊图形,是一对相邻的黑格子和蓝格子,加上与它们连通的一个白格子和一个蓝格子。

思考建图,由这些格子之间的依赖关系可以猜到是个最小割。

假设有一个蓝格子 A 和与其相邻的一个黑格子 B,与他们直接相连的白色和红色格子都有方块,那么我们需要选择下列三种操作的至少一种:

1. 删掉所有白格子

2. 删掉所有红格子

3. 删掉 A 和 B 其中之一

因此得到建图:S 像所有红格子连一条流量为红格子费用的边,红格子向相邻有方块的蓝格子连一条流量为 inf 的边,蓝格子向相邻黑格子连一条流量为 min(蓝格子费用,黑格子费用)的边,黑格子向相邻白格子连一条流量为 inf 的边,白格子向 T 连一条流量为白格子费用的边。

最小割即为答案。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
typedef long long LL;
const int N=100010,inf=0x3f3f3f3f;
int n,m,K,cnt,S,T,ans,tot=1;
map<LL,int> mp;
int X[N],Y[N],Z[N],col[N];
int lev[N],q[N],h[N<<3],ne[N<<3],flow[N<<3],to[N<<3];
int mvx[5]={1,-1,0,0},mvy[5]={0,0,1,-1};

LL id(LL x,LL y) {return (x-1)*m+y;}
void add(int x,int y,int z) {
    to[++tot]=y,ne[tot]=h[x],h[x]=tot,flow[tot]=z;
    to[++tot]=x,ne[tot]=h[y],h[y]=tot,flow[tot]=0;
}
int dfs(int x,int liu) {
    if(x==T) return liu;
    int sum=0;
    for(RI i=h[x];i;i=ne[i])
        if(flow[i]>0&&lev[to[i]]==lev[x]+1) {
            int kl=dfs(to[i],min(flow[i],liu-sum));
            sum+=kl,flow[i]-=kl,flow[i^1]+=kl;
            if(sum==liu) return sum;
        }
    if(!sum) lev[x]=-1;
    return sum;
}
int bfs() {
    for(RI i=1;i<=cnt;++i) lev[i]=0;
    int he=1,ta=1;q[1]=S,lev[S]=1;
    while(he<=ta) {
        int x=q[he];++he;
        if(x==T) return 1;
        for(RI i=h[x];i;i=ne[i])
            if(flow[i]>0&&!lev[to[i]])
                lev[to[i]]=lev[x]+1,q[++ta]=to[i];
    }
    return 0;
}

void work_black(int x,int y,int k1) {
    for(RI i=0;i<4;++i) {
        int tx=x+mvx[i],ty=y+mvy[i];
        if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&mp[id(tx,ty)]) {
            int k2=mp[id(tx,ty)];
            if(col[k2]==3) add(k2,k1,min(Z[k1],Z[k2]));
            else add(k1,k2,inf);
        }
    }
}
void work_blue(int x,int y,int k1) {
    for(RI i=0;i<4;++i) {
        int tx=x+mvx[i],ty=y+mvy[i];
        if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&mp[id(tx,ty)]) {
            int k2=mp[id(tx,ty)];
            if(col[k2]!=2) add(k2,k1,inf);
        }
    }
}
int main()
{
    n=read(),m=read(),K=read();
    for(RI i=1;i<=K;++i)
        X[i]=read(),Y[i]=read(),Z[i]=read(),mp[id(X[i],Y[i])]=++cnt;
    S=++cnt,T=++cnt;
    for(RI i=1;i<=K;++i) {
        if(X[i]%4==1) col[i]=(Y[i]&1?2:4);
        else if(X[i]%4==2) col[i]=(Y[i]&1?3:1);
        else if(X[i]%4==3) col[i]=(Y[i]&1?1:3);
        else col[i]=(Y[i]&1?4:2);
    }
    for(RI i=1;i<=K;++i) {
        if(col[i]==2) work_black(X[i],Y[i],i);
        else if(col[i]==3) work_blue(X[i],Y[i],i);
        else if(col[i]==1) add(S,i,Z[i]);
        else add(i,T,Z[i]);
    }
    while(bfs()) ans+=dfs(S,inf);
    printf("%d\n",ans);
    return 0;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

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