神仙题啊……不看题解我可能一年都不一定做得出来……FlashHu大佬太强啦
到底是得有怎样的脑回路才能一眼看去就是费用流啊……
建好图之后套个板子就好了，那么我们着重来讨论一下怎么建图
首先，对于每一个水管的支管，有且仅有一个其他支管与他相连，那么就不会漏水了。用网络流的说法，就是要每个支管容量只能为1且必须满流
然而因为最优情况图可能会被分成好几个连通块，于是我们得强制所有相邻的格子都有流量才行（就是确保连通块不管怎么划分都能流）
那么黑白染色冷静一下……黑点连源，白点连汇
然后费用是因为旋转产生的……然后因为和四周都有连边所以要拆点
把每一个点拆成上下左右中，中间为原点，四周代表四个方向的水管。中间点连上源或汇，四周的点分别向能到达的接触点连边，容1费0
然后讨论旋转产生的费用……坐稳了……
先是直线型
比如射线指向上面，那么就让左下右的点连上面，左右点连边容1费1（转一次就行），下面的点连边容1费2（要转两次）
然后直角的
转一次会变成这样
那么就可以看做是上面的点跑到下面来了，那么上下建一条容1费1的边就好，左右同理。如果转了两次，刚好可以从上右一起流，费2，所以不用新加边了
最后第三种
如果顺时针转一次相当于左边到了下面，于是连边容1费1，同理下右连边容1费1，上下连边容1费2（因为上下转换要转两次）
然后其他都和以上一样分类讨论就行了
上代码吧，写的zkw费用流
//minamoto
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
inline int read(){
#define num ch-'0'
char ch;bool flag=;int res;
while(!isdigit(ch=getc()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getc());res=res*+num);
(flag)&&(res=-res);
#undef num
return res;
}
#define UP(x) x+turn*sum
#define RI(x) x+((turn+1)&3)*sum
#define DO(x) x+((turn+2)&3)*sum
#define LE(x) x+((turn+3)&3)*sum
#define MD(x) x+(sum<<2)//上面几个用来计算对应点的数组下标，上下左右中。。。
const int N=,M=;
int sum,S=,T;
int head[N],Next[M],ver[M],edge[M],cost[M],tot=;
int dis[N],vis[N],cur[N],ans;
int n,m,k=,totf,turn;
inline void add(int u,int v,int e,int c,int tp){
//tp表示点的颜色，如果是白点所有边都要反向，为了让流流向汇点
if(tp) u^=v^=u^=v;
ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e,cost[tot]=c;
ver[++tot]=u,Next[tot]=head[v],head[v]=tot,edge[tot]=,cost[tot]=-c;
}
queue<int> q;
bool spfa(){
memset(dis,-,sizeof(dis));
memset(vis,,sizeof(vis));
memcpy(cur,head,sizeof(int)*(T-S+));
q.push(T),dis[T]=,vis[T]=;
while(!q.empty()){
int u=q.front();q.pop(),vis[u]=;
for(int i=head[u];i;i=Next[i])
if(edge[i^]){
int v=ver[i],c=cost[i];
if(dis[v]<||dis[v]>dis[u]-c){
dis[v]=dis[u]-c;
if(!vis[v]) vis[v]=,q.push(v);
}
}
}
return ~dis[S];
}
int dfs(int u,int limit){
if(u==T||!limit) return limit;
int flow=,f;vis[u]=;
for(int &i=cur[u];i;i=Next[i]){
int v=ver[i];
if(dis[v]==dis[u]-cost[i]&&!vis[v]&&(f=dfs(v,min(limit,edge[i])))){
flow+=f,limit-=f;
edge[i]-=f,edge[i^]+=f;
ans+=f*cost[i];
if(!limit) break;
}
}
vis[u]=;
return flow;
}
int zkw(){
//zkw费用流板子
int flow=;
while(spfa()) flow+=dfs(S,inf);
return flow;
}
int main(){
// freopen("testdata.in","r",stdin);
n=read(),m=read();
sum=n*m,T=sum*+;
for(int i=;i<n;++i)
for(int j=;j<m;++j,++k){
turn=;
int t=(i+j)&;
t?add(S,MD(k),inf,,):add(MD(k),T,inf,,);
if(i) add(DO(k-m),UP(k),,,t);
if(j) add(RI(k-),LE(k),,,t);
int op=read();
if(op&) add(UP(k),MD(k),,,t),++totf;
if(op&) add(RI(k),MD(k),,,t),++totf;
if(op&) add(DO(k),MD(k),,,t),++totf;
if(op&) add(LE(k),MD(k),,,t),++totf;
//统计一下总流量顺便和中间点连边
//因为每条边被记了两次，到时候要除以2
switch(op){
//直接把所有相同类型的一起处理掉
case :++turn;
case :++turn;
case :++turn;
case :
add(RI(k),UP(k),,,t);
add(DO(k),UP(k),,,t);
add(LE(k),UP(k),,,t);
break;
case :++turn;
case :++turn;
case :++turn;
case :
add(DO(k),UP(k),,,t);
add(LE(k),RI(k),,,t);
break;
case :++turn;
case :++turn;
case :++turn;
case :
add(DO(k),LE(k),,,t);
add(DO(k),UP(k),,,t);
add(DO(k),RI(k),,,t);
break;
}
}
printf("%d\n",(zkw()<<)==totf?ans:-);
return ;
}