oj:https://gxyzoj.com/d/gxyznoi/p/P93
它要判断什么时候不漏水，就是需要建一种图，使得原图的最大流是答案
因为是网格图，考虑黑白染色，可以将\((i+j)\)对2取模的结果作为颜色，将所有颜色为1的点向源点连边，颜色为0的点向汇点连边
接下来考虑如何判断是否漏水，因为有四个方向，考虑拆点
将每个点拆为上下左右四个周围点和一个中间点，然后此时就可以将能流到的方向与其对应的点相连
接下来考虑旋转，虽然原图共有15种情况，实则可以分成5大类
- 一条出边
上图中的边朝上，所以向右或向左均需转一次，而向下需转两次，所以可以从上向左和有分别连一条边权为1的边，向下连一条边权为2的边
- 直线型
因为无法旋转，直接连边即可
- L型
显然，转一次可以使朝上的边向下或使朝右的边向左，所以可以从上向下，从右向左分别连一条边权为1的边
接着考虑旋转2次的情况，其实就是将两条边跑满，所以不用另外建边
- 三条出边
和一条出边类似，将左或右转到下方需要1次，上方的转到下方需要2次
- 十字型
显然不需要旋转
此时，求费用即可
代码：
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int inf=1e9;
int n,m,head[20005],edgenum=1,s,t;
struct edge{
int to,nxt,val,flow;
}e[5000006];
void add_edge(int u,int v,int f,int w)
{
e[++edgenum].nxt=head[u];
e[edgenum].to=v;
e[edgenum].val=w;
e[edgenum].flow=f;
head[u]=edgenum;
}
void link(int u,int v,int f,int w)
{
add_edge(u,v,f,w);
add_edge(v,u,0,-w);
}
int id(int x,int y,int tmp)
{
return (x-1)*m*5+(y-1)*5+tmp;
}
// mid=5,right=2/1,up=1/10,left=4/100,down=3/1000
int dx[5]={-1,0,0,1},dy[5]={0,-1,1,0};
int c1[5]={1,4,2,3},c2[5]={3,2,4,1};
int sum;
void link1(int x,int y,int z,int col)
{
if(col)
{
link(s,id(x,y,5),inf,0);
for(int i=0;i<4;i++)
{
int tx=x+dx[i],ty=y+dy[i];
if(tx<1||ty<1||tx>n||ty>m) continue;
link(id(x,y,c1[i]),id(tx,ty,c2[i]),1,0);
}
for(int i=0;i<4;i++)
{
if((1<<i)&z)
{
link(id(x,y,5),id(x,y,i+1),1,0);
sum++;
}
}
if(z==1)//1
{
link(id(x,y,1),id(x,y,2),1,1);
link(id(x,y,1),id(x,y,3),1,2);
link(id(x,y,1),id(x,y,4),1,1);
}
if(z==2)//10
{
link(id(x,y,2),id(x,y,4),1,2);
link(id(x,y,2),id(x,y,3),1,1);
link(id(x,y,2),id(x,y,1),1,1);
}
if(z==4)//100
{
link(id(x,y,3),id(x,y,1),1,2);
link(id(x,y,3),id(x,y,2),1,1);
link(id(x,y,3),id(x,y,4),1,1);
}
if(z==8)//1000
{
link(id(x,y,4),id(x,y,1),1,1);
link(id(x,y,4),id(x,y,2),1,2);
link(id(x,y,4),id(x,y,3),1,1);
}
if(z==3)//10+1
{
link(id(x,y,1),id(x,y,3),1,1);
link(id(x,y,2),id(x,y,4),1,1);
}
if(z==6)//100+10
{
link(id(x,y,2),id(x,y,4),1,1);
link(id(x,y,3),id(x,y,1),1,1);
}
if(z==9)//1000+1
{
link(id(x,y,1),id(x,y,3),1,1);
link(id(x,y,4),id(x,y,2),1,1);
}
if(z==12)//1000+100
{
link(id(x,y,4),id(x,y,2),1,1);
link(id(x,y,3),id(x,y,1),1,1);
}
if(z==7)//100+10+1
{
link(id(x,y,1),id(x,y,4),1,1);
link(id(x,y,2),id(x,y,4),1,2);
link(id(x,y,3),id(x,y,4),1,1);
}
if(z==11)//1000+10+1
{
link(id(x,y,1),id(x,y,3),1,2);
link(id(x,y,2),id(x,y,3),1,1);
link(id(x,y,4),id(x,y,3),1,1);
}
if(z==13)//1000+100+1
{
link(id(x,y,1),id(x,y,2),1,1);
link(id(x,y,3),id(x,y,2),1,1);
link(id(x,y,4),id(x,y,2),1,2);
}
if(z==14)//1000+100+10
{
link(id(x,y,2),id(x,y,1),1,1);
link(id(x,y,3),id(x,y,1),1,2);
link(id(x,y,4),id(x,y,1),1,1);
}
}
else
{
link(id(x,y,5),t,inf,0);
for(int i=0;i<4;i++)
{
if((1<<i)&z)
{
link(id(x,y,i+1),id(x,y,5),1,0);
sum++;
}
}
if(z==1)//1
{
link(id(x,y,2),id(x,y,1),1,1);
link(id(x,y,3),id(x,y,1),1,2);
link(id(x,y,4),id(x,y,1),1,1);
}
if(z==2)//10
{
link(id(x,y,4),id(x,y,2),1,2);
link(id(x,y,3),id(x,y,2),1,1);
link(id(x,y,1),id(x,y,2),1,1);
}
if(z==4)//100
{
link(id(x,y,1),id(x,y,3),1,2);
link(id(x,y,2),id(x,y,3),1,1);
link(id(x,y,4),id(x,y,3),1,1);
}
if(z==8)//1000
{
link(id(x,y,1),id(x,y,4),1,1);
link(id(x,y,2),id(x,y,4),1,2);
link(id(x,y,3),id(x,y,4),1,1);
}
if(z==3)//10+1
{
link(id(x,y,4),id(x,y,2),1,1);
link(id(x,y,3),id(x,y,1),1,1);
}
if(z==6)//100+10
{
link(id(x,y,1),id(x,y,3),1,1);
link(id(x,y,4),id(x,y,2),1,1);
}
if(z==9)//1000+1
{
link(id(x,y,2),id(x,y,4),1,1);
link(id(x,y,3),id(x,y,1),1,1);
}
if(z==12)//1000+100
{
link(id(x,y,1),id(x,y,3),1,1);
link(id(x,y,2),id(x,y,4),1,1);
}
if(z==7)//100+10+1
{
link(id(x,y,4),id(x,y,1),1,1);
link(id(x,y,4),id(x,y,2),1,2);
link(id(x,y,4),id(x,y,3),1,1);
}
if(z==11)//1000+10+1
{
link(id(x,y,3),id(x,y,1),1,2);
link(id(x,y,3),id(x,y,2),1,1);
link(id(x,y,3),id(x,y,4),1,1);
}
if(z==13)//1000+100+1
{
link(id(x,y,2),id(x,y,1),1,1);
link(id(x,y,2),id(x,y,3),1,1);
link(id(x,y,2),id(x,y,4),1,2);
}
if(z==14)//1000+100+10
{
link(id(x,y,1),id(x,y,2),1,1);
link(id(x,y,1),id(x,y,3),1,2);
link(id(x,y,1),id(x,y,4),1,1);
}
}
}
int flow[20005],dis[20005],pre[20005],pos[20005];
bool inq[20005];
queue<int> q;
bool spfa(int x,int y)
{
for(int i=0;i<=t;i++)
{
dis[i]=flow[i]=inf,inq[i]=0;
}
q.push(x);
dis[x]=0;
inq[x]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
inq[u]=0;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to,w=e[i].val,f=e[i].flow;
if(f&&dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
flow[v]=min(flow[u],f);
pre[v]=u,pos[v]=i;
if(!inq[v])
{
inq[v]=1;
q.push(v);
}
}
}
}
if(dis[y]<inf) return 1;
return 0;
}
int cost,cnt;
void MCMF()
{
cost=cnt=0;
while(spfa(s,t))
{
cnt+=flow[t];
cost+=flow[t]*dis[t];
int x=t;
while(x!=s)
{
int p=pos[x];
e[p].flow-=flow[t];
e[p^1].flow+=flow[t];
x=pre[x];
}
}
}
int main()
{
scanf("%d%d",&n,&m);
t=n*m*5+5;
for(int i=1;i<=n;i++)
{
int col=i%2;
for(int j=1;j<=m;j++)
{
int x;
scanf("%d",&x);
link1(i,j,x,col);
col^=1;
}
}
MCMF();
if(cnt*2==sum)
printf("%d",cost);
else printf("-1");
return 0;
}