题目：https://www.luogu.com.cn/problem/P4003
简明题意：给你一个矩阵，每个格子都有一种水管，每种水管可以向上下左右这四个方向中的若干个给定的方向延伸，每次可以将一个格子的水管顺或逆时针旋转90°，问使水管全部闭合的最小操作次数
看起来就非常的可以最小费用最大流
既然是矩阵，那么肯定要黑白染色，向源点连白点，向汇点连黑点，然后我们考虑拆点，每个格子多拆四个接口方向的点，这样可以表示出来现在水管的状态，对于旋转可以分情况讨论
- 只有一个方向的点：该方向和和它相对的方向连费用为2的边，说明需要旋转2次；剩下的两个方向连费用为1的边，只需要旋转1次
- 有两个方向的边：这两个方向分别和和该方向相对的边连费用为1的边，旋转1次的可以表示；旋转2次的可以通过都流这两个边表示
- 有三个方向的边：将有相对边的边和对边连费用为2的边，说明需要旋转2次；剩下的两个边向没有方向的边连费用为1的边，只需要旋转1次
- 四个方向的边不需要旋转，只有对着的方向的边不能旋转
相邻的格子在对应方向上连边
然后我们记录下所有格子方向的个数和(tot)，(tot/2=flow)说明有解，因为两个水管的接口合上成一个了，否则无解
刚才的连边过程实际上是把旋转中重合的边略去了，画画图就可以很好理解了
我是分情况讨论的，没有用也不会用什么高超的位运算技巧QAQ
Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 2e3;
const int M = 114514;
const int inf = 19260817;
using namespace std;
struct edges
{
int to,cost,f;
}edge[M * 2 + 5];
int nc,tot,num[M + 5],mf,p[M + 5],n,m,a[N + 5],ans,mp[N + 5][N + 5],id[N + 5][N + 5],id_cnt,co[N + 5][N + 5],S,T,nxt[M + 5],head[M + 5],edge_cnt = 1,dis[M + 5],vis[M + 5],q[M + 5],cur[M + 5];
void add_edge(int u,int v,int w,int f)
{
edge[++edge_cnt] = (edges){v,w,f};
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
}
void add(int u,int v,int w,int f)
{
if (!nc)
swap(u,v);
add_edge(u,v,w,f);
add_edge(v,u,0,-f);
}
void add_chai(int S,int x)
{
add(S,x * 5,inf,0);
if (a[x] & 1)
add(x * 5,x * 5 + 1,1,0);
if (a[x] & 2)
add(x * 5,x * 5 + 2,1,0);
if (a[x] & 4)
add(x * 5,x * 5 + 3,1,0);
if (a[x] & 8)
add(x * 5,x * 5 + 4,1,0);
}
void rev(int x)
{
if (a[x] == 1)
add(x * 5 + 1,x * 5 + 2,1,1),add(x * 5 + 1,x * 5 + 4,1,1),add(x * 5 + 1,x * 5 + 3,1,2);
else
if (a[x] == 2)
add(x * 5 + 2,x * 5 + 1,1,1),add(x * 5 + 2,x * 5 + 3,1,1),add(x * 5 + 2,x * 5 + 4,1,2);
else
if (a[x] == 3)
add(x * 5 + 1,x * 5 + 3,1,1),add(x * 5 + 2,x * 5 + 4,1,1);
else
if (a[x] == 4)
add(x * 5 + 3,x * 5 + 2,1,1),add(x * 5 + 3,x * 5 + 4,1,1),add(x * 5 + 3,x * 5 + 1,1,2);
else
if (a[x] == 6)
add(x * 5 + 3,x * 5 + 1,1,1),add(x * 5 + 2,x * 5 + 4,1,1);
else
if (a[x] == 7)
add(x * 5 + 2,x * 5 + 4,1,2),add(x * 5 + 1,x * 5 + 4,1,1),add(x * 5 + 3,x * 5 + 4,1,1);
else
if (a[x] == 8)
add(x * 5 + 4,x * 5 + 1,1,1),add(x * 5 + 4,x * 5 + 3,1,1),add(x * 5 + 4,x * 5 + 2,1,2);
else
if (a[x] == 9)
add(x * 5 + 1,x * 5 + 3,1,1),add(x * 5 + 4,x * 5 + 2,1,1);
else
if (a[x] == 11)
add(x * 5 + 1,x * 5 + 3,1,2),add(x * 5 + 4,x * 5 + 3,1,1),add(x * 5 + 2,x * 5 + 3,1,1);
else
if (a[x] == 12)
add(x * 5 + 4,x * 5 + 2,1,1),add(x * 5 + 3,x * 5 + 1,1,1);
else
if (a[x] == 13)
add(x * 5 + 4,x * 5 + 2,1,2),add(x * 5 + 1,x * 5 + 2,1,1),add(x * 5 + 3,x * 5 + 2,1,1);
else
if (a[x] == 14)
add(x * 5 + 3,x * 5 + 1,1,2),add(x * 5 + 4,x * 5 + 1,1,1),add(x * 5 + 2,x * 5 + 1,1,1);
}
int dfs(int u,int flow)
{
if (u == T)
return flow;
int sum = 0;
p[u] = 1;
for (int &i = cur[u];i;i = nxt[i])
{
int v = edge[i].to,w = edge[i].cost,f = edge[i].f;
if (w && dis[u] + f == dis[v] && !p[v])
{
int res = dfs(v,min(flow,w));
edge[i].cost -= res;
edge[i ^ 1].cost += res;
flow -= res;
sum += res;
mf += res * f;
if (!flow)
break;
}
}
return sum;
}
int spfa()
{
for (int i = 1;i <= id_cnt * 5 + 4;i++)
cur[i] = head[i],vis[i] = 0,dis[i] = inf,p[i] = 0;
dis[S] = 0;
vis[S] = 1;
int l = 1,r = 0;
q[++r] = S;
while (l <= r)
{
int u = q[l++];
vis[u] = 0;
for (int i = head[u];i;i = nxt[i])
{
int v = edge[i].to,w = edge[i].cost,f = edge[i].f;
if (w && dis[u] + f < dis[v])
{
dis[v] = dis[u] + f;
if (!vis[v])
{
q[++r] = v;
vis[v] = 1;
}
}
}
}
return dis[T];
}
int main()
{
scanf("%d%d",&n,&m);
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
id[i][j] = ++id_cnt,co[i][j] = (i + j) % 2;
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
scanf("%d",&a[id[i][j]]);
for (int i = 1;i <= 15;i++)
for (int j = 0;j < 4;j++)
if (i & (1 << j))
num[i]++;
S = 1;
T = 2;
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
{
nc = co[i][j];
if (co[i][j] == 1)
add_chai(S,id[i][j]);
else
add_chai(T,id[i][j]);
tot += num[a[id[i][j]]];
rev(id[i][j]);
if (id[i - 1][j])
add(id[i][j] * 5 + 1,id[i - 1][j] * 5 + 3,1,0);
if (id[i][j - 1])
add(id[i][j] * 5 + 4,id[i][j - 1] * 5 + 2,1,0);
}
int ans = 0;
while (spfa() != inf)
ans += dfs(S,inf);
if (tot / 2 == ans)
printf("%d
",mf);
else
printf("-1
");
return 0;
}