题解 P3756 【[CQOI2017]老C的方块】
shadowice1984 · · 题解
（不放代码的题解真的棒？）
这道题请大家相信信仰!相信dinic！O(V^2E)是最坏复杂度，当图的深度相当小， 相当稀疏的时候，dinic跑的绝对是飞起的！
建图推出来不是结束，染色也很关键！
网络流题的几个特性
1.题面偏长
2.会出现网格图
3.有鬼畜的设定，并且如果想到了错解的话这些设定完全没必要
(例如P4004无限之环，如果不是有某一个奇怪的设定的话网络流完全做不了)
那么我们呢发现这道题的设定也非常鬼畜
有一个关键边，还有一堆奇怪的图形……
但是操作异常简单，只有炸格子这一种操作
还是网格图……如果你足够熟练（我怎么这么不熟练啊……）的话此时的第一反应应该是黑白染色，然后考虑建图了。
有了可以染的色。又有了可以切题的板子。两件快乐事情重合在一起。而这两份快乐，又给我带来更多的快乐。得到的，本该是像水一般好切的题……但是，为什么，会变成这样呢……
黑白染色EX：四色
但是我们很快发现仅仅是黑白染色不足以让我们切掉这道题，因为和蓝边是否相邻显然对于一个格子是很重要的，于是我们再以是否挨着蓝边为根据继续染色，发现我们可以染成这个样子
我们发现题目中所给出的奇怪图形，全部是4个格子为4种不同颜色且红蓝点相邻的图形！
也就是说我们对于一个联通块来说我们需要炸光其中的一种颜色才可以破坏给定的图形，那么我们从最小割的角度来讲就是破坏其中的一段通路即可
那么这个染色图形已经给了我们很大的启示了，我们发现黄色点和蓝色点不直接相连，绿色点和红色点不直接相连
由于形成图形必须有相邻的红蓝点，因此黄点和绿点之间连边似乎没啥必要
那么我们发现此时这样一种建图方式可以极好的满足我们的要求
由于破坏节点只可能是爆黄点，爆绿点，爆红蓝间的最小点中3选一因此对于每一个红蓝组，我们需要想方设法构造一个S到T的通路，使得这三个路径串联在一起。同时，显然我们必须爆掉所有的黄点或者绿点，因此3个黄和3个绿应该是并联的
在最小割中，串联表示“或”，并联表示“且”
大概按照我们的想法连的边应该是这样？
其中红蓝间的边是红蓝点权的最小值，本来正规的连法是加一个中间点，连向红的是红点权，连向蓝的是蓝点权表示既可以爆红也可以爆蓝，但是这里直接被缩成一条边了
显然红黄，蓝绿的联系是无法斩断的，所以设成无穷大好了
那么我们让每个黄点向S连等于其容量的边，每个绿点向T连等于其容量的边就成功的建出了一个最小割模型！我们现在只需跑一个裸的最小割就行了！
但是有一个问题，一般网格图题，我们为了好写，会维护一个tr数组来给方格编号，染色，但是这里的r,c都是1e5这使我们没法很好的染色……
另外，我们还发现，这个色染得可谓是奇技淫巧，毫无规律可言，不像黑白染色那样判断(x+y)%2般优美……，难道我们需要换一个更加优美的算法？
分8种情况枚举x%4和y%2的组合即可
另外，我们发现肯定不允许我们开一个二维数组保存格子里是否有点，因此我们需要map，具体来讲把两个int的坐标利用(i-1)*c+j这个公式强行映射到longlong上，然后用map存下坐标和编号的联系，毕竟1e5的情况下logN的查找复杂度可以接受，之后我们暴力检测每一个红蓝节点周边节点颜色建图即可
对了这里强行安利一波switch这个平时用不到的语法，虽说可以被else if完爆，但是不用写括号！不用写括号！代码紧凑！如果写网络流这种本来染色就复杂的东西来说实在是再好不过了……
这题的代码实现需要一些技巧……主要是染色很棒(๑•̀ㅂ•́)و✧，这里为了判越界的时候不用讨论特地把映射公式变成了(i-1)*(c+1)+j这样的话即使是y超界的话也会被直接判掉……
上代码~
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;//dinic板子还不熟练的话去看膜板的题解吧……
const int N=1e5+10;const int M=6*1e6+50;
struct data{int v;int nxt;int cot;}edge[M];
int alist[N];int cnt=1;int res;
inline void add(int u,int v,int cot)
{
edge[++cnt].v=v;edge[cnt].nxt=alist[u];alist[u]=cnt;edge[cnt].cot=cot;
edge[++cnt].v=u;edge[cnt].nxt=alist[v];alist[v]=cnt;edge[cnt].cot=0;
}
int dep[N];queue <int> q;int ctt;int s;int t;
inline bool bfs()
{
for(int i=1;i<=ctt;i++){dep[i]=0x3f3f3f3f;}
dep[s]=0;q.push(s);
while(!q.empty())
{
int now=q.front();q.pop();int nxt=alist[now];
while(nxt)
{
int v=edge[nxt].v;int cot=edge[nxt].cot;
if(dep[v]==0x3f3f3f3f&&cot!=0)
{dep[v]=dep[now]+1;q.push(v);}
nxt=edge[nxt].nxt;
}
}return dep[t]!=0x3f3f3f3f;
}
inline int dfs(int x,int lim)
{
if(x==t){return lim;}
int nxt=alist[x];int nowflow=0;
while(nxt)
{
if(lim==0)break;
int v=edge[nxt].v;int cot=edge[nxt].cot;
if(dep[v]==dep[x]+1&&cot!=0)
{
int del=dfs(v,min(lim,cot));
lim-=del;nowflow+=del;
edge[nxt].cot-=del;edge[nxt^1].cot+=del;
}nxt=edge[nxt].nxt;
}if(nowflow==0){dep[x]=0x3f3f3f3f;}
return nowflow;
}//下面是染色阶段~
int n;ll r;ll c;int x[N];int y[N];int w[N];int col[N];//强行映射的公式
inline ll tr(ll i,ll j){return (i-1)*(c+1)+j;}map <ll,int> mp;
int dx[4]={1,-1,0,0};int dy[4]={0,0,-1,1};//似乎上次见到这个数组还是在写bfs走迷宫？
inline void build_A(int i,int j,int nod)//红色节点连边函数
{
for(int k=0;k<=3;k++)//枚举方向
{
ll px=dx[k]+i;ll py=dy[k]+j;int num=mp[tr(px,py)];
if(num!=0)//如果存在这个点
{
if(col[num]!=2){add(num,nod,0x3f3f3f3f);}//黄-红
else {add(nod,num,min(w[num],w[nod]));}//红-蓝
}
}
}
inline void build_B(int i,int j,int nod)//蓝色节点连边函数
{
for(int k=0;k<=3;k++)
{
ll px=dx[k]+i;ll py=dy[k]+j;int num=mp[tr(px,py)];
if(num!=0)//如果这个点存在
{if(col[num]!=1){add(nod,num,0x3f3f3f3f);}}//蓝-绿
}
}
int main()
{
scanf("%lld%lld%d",&c,&r,&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&x[i],&y[i],&w[i]);
mp[tr(x[i],y[i])]=++ctt;//强行使用map进行编号
}s=++ctt;t=++ctt;
for(int i=1;i<=n;i++)//分8中情况讨论染色
{
switch(x[i]%4)//switch+条件表达式成功挽救了不知道会有多长的ifelse
{
case 1:{col[i]=(y[i]%2)?1:3;break;}
case 2:{col[i]=(y[i]%2)?2:4;break;}
case 3:{col[i]=(y[i]%2)?4:2;break;}
case 0:{col[i]=(y[i]%2)?3:1;break;}
}
}
for(int i=1;i<=n;i++)//分4种情况建图
{
switch(col[i])
{
case 1:{build_A(x[i],y[i],i);break;}
case 2:{build_B(x[i],y[i],i);break;}
case 3:{add(s,i,w[i]);break;}//S-黄
case 4:{add(i,t,w[i]);break;}//绿-T
}
}while(bfs()){res+=dfs(s,0x3f3f3f3f);}
printf("%d",res);return 0;//拜拜程序~
}