P3756题解

· · 题解

Update 修改了错别字。

在做这道题前，建议先做 P2774 方格取数问题 和 P3355 骑士共存问题 以保证您会染色网络流。

一道染色题的究极形态。

首先看到方格想网络流。看到要欧拉掉点代价最小就可以想最小割了。最小割，又是在网格中，染色没跑了。

那么，我们进行黑白染色——

然后就会发现染完后什么用都没有。

难道是这道题不能用染色？

然后我们来看那四个老 C 不喜欢的图形，都是四个方块组成的。

而且——

我们发现，假如我们用四个颜色蓝绿红黄对这四个图形进行染色的话，就会发现，一定会存在这样一条路径：黄—蓝—特殊边—绿—红。

有一点网络流的味道了。

试想一下，假设我们按 源点—黄—蓝—特殊边—绿—红—汇点 连边的话，假若图还连通就说明还有这种图形。必须把这个图变成不连通然后花费最小代价，这不就是最小割吗。

那么现在问题就是如何连层与层的边以及边权的问题了。

这就很简单了。

我们刚刚说一个不喜欢图形中的路径是黄—蓝—特边—绿—红，那就说明每一个蓝点只能由黄点溜过来，每一个特殊边只能由蓝点流过来，后面几层同理，所以就向黄点周围所有蓝点连边，所有蓝点向特殊边连，后面几层同理。

那么边权呢？

如果把一个黄点欧拉掉了，那么周围所有蓝点就都不可以通过这个黄点组成讨厌图形了。蓝点欧拉掉了特殊边也就不能组成特殊图形了。一下几层同理。

说明边权不在黄—蓝，绿—红而在黄—源点，蓝—特边，绿—特边，红—汇点上。回推一下这也是符合题意的。把黄点与源点的边割掉了就说明不选这个黄点，它连的所有蓝点都不会通过它产生不喜欢图形。那么，我们把上述 4 种边的边权改成欧拉这个方块的代价，其余边全是 INF 就好了。然后我们发现，蓝—特殊边—绿 这一条路径其实和 蓝—绿 然后边权为 \min(val[Blue],val[Green]) 是等价的（因为每条特殊边最多只有一个蓝点和绿点和它连边），这样就顺便把特殊边这一层给优化掉了。

那么就还剩最后一个问题了。怎么染色让这个图中不管不喜欢图形怎么摆都是按以上路径的？

这个吗没什么技巧，多试试几次就出来了。总之就是这样染色的：

然后就会发现这个图的循环规律是每个 2 \times 4 的长方形都是一样的，然后就对每一个长方形内八个不同格子进行特判就好了。

然后就是一些零零碎碎的问题：

第一个，怎么存每一个格子所建的节点。

按照以往的我们直接用列乘上 10 的幂再加上行然后直接用数组存肯定是木大的，这个图很贴心的给出了长宽小于 10^5 ,所以不得不建一个 <long long,int> 的 map 来强行让每一个格子的坐标（按刚刚的方法把坐标处理成 long long ）与一个节点编号对应。

第二个，怎么比较快连边。

黄点和红点都是可以直接在读入时就直接向源汇连边的；蓝点和绿点在读入时记录一下然后读入完后再向周围的点连边好了。

code：（记住蓝点连边有两套不同方法，绿点连边也有两套不同方法，我为这个调了一个晚上）

#include<bits/stdc++.h>
#define maxx 2000001
#define B 1
#define G 2
#define R 3
#define Y 4
#define S 1999999
#define T 2000000
using namespace std;
map<long long,long long>check;
map<long long,long long>cost_;
long long r,c,n;
struct node
{
    long long col,val,x,y;
}N[maxx];
long long fi[maxx],nx[maxx],to[maxx],val[maxx],depth[maxx],tot=1,num,heroes[maxx],b_g;
long long dx[4]={-1,0,0,1};
long long dy[4]={0,1,-1,0};
void link(long long a,long long b,long long c)
{
    nx[++tot]=fi[a];
    fi[a]=tot;
    to[tot]=b;
    val[tot]=c;
}
bool bfs()
{
    memset(depth,0,sizeof(depth));
    queue<long long>que;
    que.push(S);
    depth[S]=1;
    while(!que.empty())
    {
        long long x=que.front();
        que.pop();  
        for(long long i=fi[x];i;i=nx[i])
        {
            long long v=to[i];
            if(val[i]&&!depth[v])
            {
                depth[v]=depth[x]+1;
                que.push(v);
            }
        }
    }
    return depth[T];
}
long long dinic(long long x,long long in)
{
    if(x==T)
    {
        return in;
    }
    long long out=0;
    for(long long i=fi[x];i&&in;i=nx[i])
    {
        long long v=to[i];
        if(val[i]&&depth[x]+1==depth[v])
        {
            long long res=dinic(v,min(val[i],in));
            in-=res;
            out+=res;
            val[i]-=res;    
            val[i^1]+=res;
        }
    }
    if(out==0)
    {
        depth[x]=0;
    }
    return out;
}
signed main()
{
    cin>>c>>r>>n;
    for(long long i=1;i<=n;i++)
    {
        cin>>N[i].x>>N[i].y>>N[i].val;
        long long x=N[i].x;
        long long y=N[i].y;
        check[x*1000000+y]=++num;
        switch(x%4)
        {
            case 1:
                if(y%2==1)
                {
                    N[i].col=B;
                    heroes[++b_g]=i;    
                }
                else
                {
                    N[i].col=Y;
                    link(S,num,N[i].val);
                    link(num,S,0);
                }
                break;
            case 2:
                if(y%2==1)
                {
                    N[i].col=G;
                    heroes[++b_g]=i;
                    cost_[x*1000000+y]=N[i].val;
                }
                else
                {
                    N[i].col=R;
                    link(num,T,N[i].val);
                    link(T,num,0);
                }
                break;
            case 3:
                if(y%2==1)
                {
                    N[i].col=R;
                    link(num,T,N[i].val);
                    link(T,num,0);
                }
                else
                {
                    N[i].col=G;
                    heroes[++b_g]=i;
                    cost_[x*1000000+y]=N[i].val;
                }
                break;
            case 0:
                if(y%2==1)
                {
                    N[i].col=Y;
                    link(S,num,N[i].val);
                    link(num,S,0);
                }
                else
                {
                    N[i].col=B;
                    heroes[++b_g]=i;
                }
                break;
        }
    }
    for(long long i=1;i<=b_g;i++)
    {
        long long xx=N[heroes[i]].x;
        long long yy=N[heroes[i]].y;
        if(N[heroes[i]].col==B&&xx%4==0)
        {
            if(xx+dx[0]>=1&&xx+dx[0]<=c&&yy+dy[0]>=1&&yy+dy[0]<=r)
            {
                long long s=check[(xx+dx[0])*1000000+yy+dy[0]];
                if(s)
                {
                    long long a=check[xx*1000000+yy];
                    link(a,s,min(N[heroes[i]].val,cost_[(xx+dx[0])*1000000+yy+dy[0]]));
                    link(s,a,0);
                }
            }
            for(long long i=1;i<4;i++)
            {
                if(xx+dx[i]>=1&&xx+dx[i]<=c&&yy+dy[i]>=1&&yy+dy[i]<=r&&check[(xx+dx[i])*1000000+yy+dy[i]])
                {
                    long long a=check[(xx+dx[i])*1000000+yy+dy[i]],b=check[xx*1000000+yy];
                    link(a,b,0x7ffffff);
                    link(b,a,0);
                }
            }
        }
        else if(N[heroes[i]].col==B&&xx%4==1)
        {
            if(xx+dx[3]>=1&&xx+dx[3]<=c&&yy+dy[3]>=1&&yy+dy[3]<=r)
            {
                long long s=check[(xx+dx[3])*1000000+yy+dy[3]];
                if(s)
                {
                    long long a=check[xx*1000000+yy];
                    link(a,s,min(N[heroes[i]].val,cost_[(xx+dx[3])*1000000+yy+dy[3]]));
                    link(s,a,0);
                }
            }
            for(long long i=0;i<3;i++)
            {
                if(xx+dx[i]>=1&&xx+dx[i]<=c&&yy+dy[i]>=1&&yy+dy[i]<=r&&check[(xx+dx[i])*1000000+yy+dy[i]])
                {
                    long long a=check[(xx+dx[i])*1000000+yy+dy[i]],b=check[xx*1000000+yy];
                    link(a,b,0x7ffffff);
                    link(b,a,0);
                }
            }
        }
        else if(N[heroes[i]].col==G&&xx%4==2)
        {
            for(long long i=1;i<4;i++)
            {
                if(xx+dx[i]>=1&&xx+dx[i]<=c&&yy+dy[i]>=1&&yy+dy[i]<=r&&check[(xx+dx[i])*1000000+yy+dy[i]])
                {
                    long long a=check[xx*1000000+yy],b=check[(xx+dx[i])*1000000+yy+dy[i]];
                    link(a,b,0x7ffffff);
                    link(b,a,0);
                }
            }
        }
        else
        {
            for(long long i=0;i<3;i++)
            {
                if(xx+dx[i]>=1&&xx+dx[i]<=c&&yy+dy[i]>=1&&yy+dy[i]<=r&&check[(xx+dx[i])*1000000+yy+dy[i]])
                {
                    long long a=check[xx*1000000+yy],b=check[(xx+dx[i])*1000000+yy+dy[i]];
                    link(a,b,0x7ffffff);
                    link(b,a,0);
                }
            }
        }
    }
    long long ans=0;
    while(bfs())
    {
        ans+=dinic(S,0x7ffffff);
    }
    cout<<ans;
}

对了数据有点水你输出 0 都能过掉 5 个点