4823: [Cqoi2017]老C的方块
题目：传送门
题解：
毒瘤题ORZ....
太菜了看出来是最小割啥边都不会建...狂%大佬强强强
黑白染色？不！是四个色一起染，四层图跑最小割。。。
很惊奇的发现染完色之后只要是不喜欢的图形都一定可以由黄-->黑-->红-->绿 组成
那就很nice啦...兴高采烈的去敲代码...结果10^5*10^5？？？搞毛线...太弱了ORZ，又看了一波大佬的操作，用map存！
woc...不谈了不谈了...撸撸撸（分情况分到想屎...虽然不多）
注意一下...黑到红连边的时候是不可以连inf的...然而我傻逼逼的打了...改成min(w[黑],w[红])...
代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<map>
#define inf 999999999
#define qread(x) x=read()
using namespace std;
typedef long long LL;
inline LL read()
{
LL x=,f=;char ch;
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return f*x;
}
struct node
{
int x,y,c,next,other;
}a[];int len,last[];
int n,m,T,st,ed;
void ins(int x,int y,int c)
{
int k1,k2;
k1=++len;
a[len].x=x;a[len].y=y;a[len].c=c;
a[len].next=last[x];last[x]=len; k2=++len;
a[len].x=y;a[len].y=x;a[len].c=;
a[len].next=last[y];last[y]=len; a[k1].other=k2;
a[k2].other=k1;
}
int head,tail;
int list[],h[];
bool bt_h()
{
memset(h,,sizeof(h));h[st]=;
list[]=st;head=;tail=;
while(head!=tail)
{
int x=list[head];
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(!h[y] && a[k].c)
{
h[y]=h[x]+;
list[tail++]=y;
}
}
head++;
}
if(h[ed])return true;
return false;
}
int find_flow(int x,int flow)
{
int s=,t;
if(x==ed)return flow;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(h[y]==h[x]+ && a[k].c && s<flow)
{
s+=t=find_flow(y,min(a[k].c,flow-s));
a[k].c-=t;a[a[k].other].c+=t;
}
}
if(!s)h[x]=;
return s;
}
int x[],y[],w[];//第x列，第y行，金币数
map<pair<int,int>,int>id;
int main()
{
len=;memset(last,,sizeof(last));
memset(w,,sizeof(w));
qread(n);qread(m);qread(T);st=T+;ed=st+;
for(int i=;i<=T;i++){qread(x[i]);qread(y[i]);qread(w[i]);id[make_pair(x[i],y[i])]=i;}
//黄-->黑-->红-->绿
for(int i=;i<=T;i++)
{
if(x[i]%==)//黑或黄
{
if(y[i]%==)ins(st,i,w[i]);//黄
else//黑
{
if(id[make_pair(x[i]+,y[i])])ins(id[make_pair(x[i]+,y[i])],i,inf);
if(id[make_pair(x[i],y[i]+)])ins(id[make_pair(x[i],y[i]+)],i,inf);
if(id[make_pair(x[i],y[i]-)])ins(id[make_pair(x[i],y[i]-)],i,inf);
}
}
if(x[i]%==)//黑或黄
{
if(y[i]%==)ins(st,i,w[i]);//黄
else//黑
{
//黑-->黄
if(id[make_pair(x[i],y[i]-)])ins(id[make_pair(x[i],y[i]-)],i,inf);
if(id[make_pair(x[i],y[i]+)])ins(id[make_pair(x[i],y[i]+)],i,inf);
if(id[make_pair(x[i]-,y[i])])ins(id[make_pair(x[i]-,y[i])],i,inf); //黑-->红（计算w）
if(id[make_pair(x[i]+,y[i])])
ins(i,id[make_pair(x[i]+,y[i])],min(w[i],w[id[make_pair(x[i]+,y[i])]]));
}
}
if(x[i]%==)//红或绿
{
if(y[i]%==)//红
{
if(id[make_pair(x[i],y[i]-)])ins(i,id[make_pair(x[i],y[i]-)],inf);
if(id[make_pair(x[i],y[i]+)])ins(i,id[make_pair(x[i],y[i]+)],inf);
if(id[make_pair(x[i]+,y[i])])ins(i,id[make_pair(x[i]+,y[i])],inf);
}
else ins(i,ed,w[i]);//绿
}
if(x[i]%==)//红或绿
{
if(y[i]%==)//红
{
//红-->绿
if(id[make_pair(x[i],y[i]-)])ins(i,id[make_pair(x[i],y[i]-)],inf);
if(id[make_pair(x[i],y[i]+)])ins(i,id[make_pair(x[i],y[i]+)],inf);
if(id[make_pair(x[i]-,y[i])])ins(i,id[make_pair(x[i]-,y[i])],inf); //黑-->红
if(id[make_pair(x[i]+,y[i])])
ins(id[make_pair(x[i]+,y[i])],i,min(w[i],w[id[make_pair(x[i]+,y[i])]]));
}
else ins(i,ed,w[i]);//绿
}
}
int ans=;
while(bt_h())ans+=find_flow(st,inf);
printf("%d\n",ans);
return ;
}