oj:https://gxyzoj.com/d/gxyznoi/p/P266
又是网格题，考虑染色：
显然可以发现，每一个不合法的图形都可以被染成黄->蓝->特殊边->绿->红，且旋转后同样满足条件
推广到整个棋盘就是：
所以是否可以将颜色编号，然后按照上述方法连边呢？
显然是可以的，若一个格子被填上了方块，则讨厌的形状一定满足如下条件：
-
特殊边的两边一定是被填的蓝色和绿色
-
蓝色周围有被填的黄色
-
红色周围有被填的绿色
将局部打开就是：
所以，如果要满足条件，则有四种方式：
-
删除被填的蓝色
-
删除被填的绿色
-
删除蓝色周围的黄色
-
删除绿色周围的红色
所以可以按照如下方式建图(不同的字母表示不同颜色):
此时，最小割就是答案
因为r和c比较大，可以用map记录，要么用二维map，或者用一维转换是要注意x,y的大小是否规范
代码：
#include<cstdio>
#include<map>
#include<algorithm>
#include<queue>
#include<cstring>
#define ll long long
using namespace std;
int c,r,n,s,t,edgenum=1,head[100005];
const int inf=1e9;
map<ll,int> mp;
//x->line y->row
ll id(int x,int y)
{
return 1ll*x*r-r+y;
}
struct edge{
int to,nxt,val;
}e[2000006];
void add_edge(int u,int v,int w)
{
e[++edgenum].nxt=head[u];
e[edgenum].to=v;
e[edgenum].val=w;
head[u]=edgenum;
}
void link(int u,int v,int w)
{
// printf("%d %d %d\n",u,v,w);
add_edge(u,v,w);
add_edge(v,u,0);
}
int dep[100005],cur[100005];
queue<int> q;
bool bfs(int x,int y)
{
memset(dep,0x7f,sizeof(dep));
for(int i=0;i<=t;i++) cur[i]=head[i];
while(!q.empty()) q.pop();
q.push(x);
dep[x]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(e[i].val&&dep[v]>inf)
{
dep[v]=dep[u]+1;
q.push(v);
}
}
}
if(dep[y]<inf) return 1;
return 0;
}
int dfs(int u,int flow)
{
if(u==t||flow==0) return flow;
int res=flow;
for(int i=head[u];i&&res;i=e[i].nxt)
{
int v=e[i].to,w=e[i].val;
if(dep[v]==dep[u]+1&&w>0)
{
int k=dfs(v,min(res,w));
res-=k;
e[i].val-=k;
e[i^1].val+=k;
}
}
if(res==flow) dep[u]=0;
return flow-res;
}
int x[100005],y[100005],z[100005],d[100005];
int main()
{
scanf("%d%d%d",&c,&r,&n);
s=0,t=n+1;
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&x[i],&y[i],&z[i]);
d[i]=((x[i]&3)^(y[i]&1));
mp[id(x[i],y[i])]=i;
// printf("%d\n",d[i]);
}
for(int i=1;i<=n;i++)
{
if(d[i]==0)
{
if(y[i]%2==1&&mp[id(x[i]+1,y[i])]&&x[i]<c)
{
int j=mp[id(x[i]+1,y[i])];
link(i,j,min(z[i],z[j]));
}
if(y[i]%2==0&&mp[id(x[i]-1,y[i])]&&x[i]>1)
{
int j=mp[id(x[i]-1,y[i])];
link(i,j,min(z[i],z[j]));
}
}
if(d[i]==1)
{
link(s,i,z[i]);
if(y[i]%2==1&&mp[id(x[i]+1,y[i])]&&x[i]<c)
{
int j=mp[id(x[i]+1,y[i])];
link(i,j,inf);
}
if(y[i]%2==0&&mp[id(x[i]-1,y[i])]&&x[i]>1)
{
int j=mp[id(x[i]-1,y[i])];
link(i,j,inf);
}
if(mp[id(x[i],y[i]-1)]&&y[i]>1)
{
int j=mp[id(x[i],y[i]-1)];
link(i,j,inf);
}
if(mp[id(x[i],y[i]+1)]&&y[i]<r)
{
int j=mp[id(x[i],y[i]+1)];
link(i,j,inf);
}
}
if(d[i]==2)
{
link(i,t,z[i]);
}
if(d[i]==3)
{
if(y[i]%2==1&&mp[id(x[i]+1,y[i])]&&x[i]<c)
{
int j=mp[id(x[i]+1,y[i])];
link(i,j,inf);
}
if(y[i]%2==0&&mp[id(x[i]-1,y[i])]&&x[i]>1)
{
int j=mp[id(x[i]-1,y[i])];
link(i,j,inf);
}
if(mp[id(x[i],y[i]-1)]&&y[i]>1)
{
int j=mp[id(x[i],y[i]-1)];
link(i,j,inf);
}
if(mp[id(x[i],y[i]+1)]&&y[i]<r)
{
int j=mp[id(x[i],y[i]+1)];
link(i,j,inf);
}
}
}
int ans=0;
while(bfs(s,t))
{
ans+=dfs(s,inf);
}
printf("%d",ans);
return 0;
}