题解 P3756 【[CQOI2017]老C的方块】

· · 题解

首先，看到“一个形状中如果拆掉任何一个方块都算合法”的限制，可以往最小割的方向去想。进一步说，如果我们将每个方块拆点，在拆开的点间连上一条相当于该方块权值的边；然后，对于一组四元组，假如我们可以按照某种顺序将四个东西用无穷大的边串联起来，则跑最小割即可。

现在考虑如何建图。观察到一个图形中有且仅有四个东西，于是往染四种颜色，最终的图被分成四层的方向去想。

因为每个图形中有且仅有一条特殊边，我们决定先从特殊边下手。

于是，我们初步的染色结果长这样：

然后，再进一步染色，我们得到了这样的图：

然后我们观察四种特殊图样，发现其都是一个 0 加上一个 1 加上 0 旁边的某个数加上 1 旁边的某个数；

而我们现在的图中，0 旁的数不全相等，1 旁的数同样；

于是我们考虑调整染色方式使得 0 旁所有的数都相等。

但是，这样染色后，我们发现不同的 0 旁，有的旁边全是 2，有的旁边全是 3；

所以我们考虑再次修改，得到了最终的染色方案：

在此种方案中，0 旁全是 2，1 旁全是 3。

染色完成后，我们考虑如何建图。为了防止不同的四元组间混用了边，我们必须找到一种合适的分层顺序。

因为每个 0 只会唯一地配对一个 1，而其它无论任何对之间都没有这种性质，所以我们考虑将 (0,1) 间的边放在最中间。

于是，我们最终得到的思路是从 S 连向 2 层，从 2 连向所有 0，从 0 再连向 1，从 1 连到 3，从 3 连到 T。

这样，我们便建出了图。

可是，这张图有 2\times 10^5 个点，网络流那奇奇怪怪的复杂度来跑这个确定大丈夫？

凭信仰跑就行了，反正能过

代码：

#include<bits/stdc++.h>
using namespace std;
const int lim=16384;
int n,m,k,tp[2][4]={{0,2,3,1},{2,0,1,3}},dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
namespace MaxFlow{
    const int N=210000,M=10000000;
    int head[N],cur[N],dep[N],cnt,S,T,res;
    struct node{int to,next,val;}edge[M];
    void ae(int u,int v,int w){
        edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
        edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=0,head[v]=cnt++;
    }
    queue<int>q;
    inline bool bfs(){
        memset(dep,0,sizeof(dep)),q.push(S),dep[S]=1;
        while(!q.empty()){
            register int x=q.front();q.pop();
            for(register int i=cur[x]=head[x];i!=-1;i=edge[i].next)if(edge[i].val&&!dep[edge[i].to])dep[edge[i].to]=dep[x]+1,q.push(edge[i].to);
        }
        return dep[T]>0;
    }
    bool reach;
    inline int dfs(int x,int flow){
        if(x==T){res+=flow,reach=true;return flow;}
        int used=0;
        for(register int &i=cur[x];i!=-1;i=edge[i].next){
            if(!edge[i].val||dep[edge[i].to]!=dep[x]+1)continue;
            register int ff=dfs(edge[i].to,min(edge[i].val,flow-used));
            if(ff){edge[i].val-=ff,edge[i^1].val+=ff,used+=ff;if(used==flow)break;}
        }
        return used;
    }
    inline void Dinic(){while(bfs()){reach=true;while(reach)reach=false,dfs(S,0x3f3f3f3f);}}
}
using namespace MaxFlow;
map<pair<int,int>,int>mp;
int main(){
    scanf("%d%d%d",&m,&n,&k),S=2*k+1,T=2*k+2,memset(head,-1,sizeof(head));
    for(int i=1,x,y,z;i<=k;i++){
        scanf("%d%d%d",&y,&x,&z);
        ae(i,i+k,z);
        mp[make_pair(x,y)]=i;
        if(tp[x%2][y%4]==2)ae(S,i,lim);
        if(tp[x%2][y%4]==3)ae(i+k,T,lim);
    }
    for(auto i:mp){
        int xi=i.first.first,yi=i.first.second,zi=i.second;
//      printf("%d %d %d:%d\n",xi,yi,zi,tp[xi%2][yi%4]);
        if(tp[xi%2][yi%4]>=2)continue;
        for(int I=0;I<4;I++){
            int xx=xi+dx[I],yy=yi+dy[I];
            if(mp.find(make_pair(xx,yy))==mp.end())continue;
            int zz=mp[make_pair(xx,yy)];
            if(tp[xx%2][yy%4]<=1){
                if(tp[xi%2][yi%4]==0)ae(zi+k,zz,lim);
                continue;
            }
            if(tp[xi%2][yi%4]==0)ae(zz+k,zi,lim);
            else ae(zi+k,zz,lim);
        }
    }
    Dinic();
    printf("%d\n",res);
    return 0;
}