很好的一道网络里题
首先想插头DP的还是出门左转10分代码吧
然后考虑怎么网络流
首先要保证没有漏水
也就是说每个接口一定要有对应的接口
那么发现每个点只有可能和上下左右四个点产生联通关系
所以不妨对图进行黑白染色
然后把源点连向所有的黑色格子，所有的黑色格子向白色格子连边，所有的白色格子向汇点连边
那么具体怎么处理每个格子的贡献？
把每个格子分成四个点分别表示上下左右
然后我们发现需要转动的只有三种
- 只有一个接口
- 有两个接口形成L形
- 有三个接口
然后考虑一个接口，相反方向连边代价是2，其他两个方向是1
L形，转九十度和转二百七十度是代价相等的，然后发现其实如果不考虑顺序的影响因素，本质上只有一个位置变成了另外一个位置
那么旋转180度也就是两个位置同时变化，刚好是变化一次代价为1，是不是很神奇呢
然后三个接口的情况类似，需要分类讨论，但是并不复杂，和两个的情况类似
然后建图建完了就可以费用流了
我怎么这么慢。。。
//Author: dream_maker
#include<bits/stdc++.h>
using namespace std;
//----------------------------------------------
//typename
typedef long long ll;
typedef pair<int, int> pi;
//convenient for
#define fu(a, b, c) for (int a = b; a <= c; ++a)
#define fd(a, b, c) for (int a = b; a >= c; --a)
#define fv(a, b) for (int a = 0; a < (signed)b.size(); ++a)
//inf of different typename
const int INF_of_int = 1e9;
const ll INF_of_ll = 1e18;
//fast read and write
template <typename T>
void Read(T &x) {
bool w = 1;x = 0;
char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') w = 0, c = getchar();
while (isdigit(c)) {
x = (x<<1) + (x<<3) + c -'0';
c = getchar();
}
if (!w) x = -x;
}
template <typename T>
void Write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) Write(x / 10);
putchar(x % 10 + '0');
}
//----------------------------------------------
const int N = 1.6e7 + 10;
const int M = 2e3 + 10;
namespace Min_Cost_Max_Flow {
struct Edge{
int u, v, cap, flow, cost;
};
int S, T;
int dis[N], pre[N], f[N];
bool inq[N];
vector<Edge> E;
vector<int> G[N];
void add(int u, int v, int cap, int cost) {
E.push_back((Edge){u, v, cap, 0, cost});
E.push_back((Edge){v, u, 0, 0, -cost});
int m = E.size();
G[u].push_back(m - 2);
G[v].push_back(m - 1);
}
bool spfa(int &flow, int &cost) {
static queue<int> q;
fu(i, 1, T) dis[i] = INF_of_int;
dis[S] = 0;
f[S] = INF_of_int;
q.push(S);
while(!q.empty()){
int u = q.front();q.pop();
inq[u] = 0;
fv(i, G[u]) {
Edge e = E[G[u][i]];
if (e.cap > e.flow && dis[e.v] > dis[u] + e.cost) {
dis[e.v] = dis[u] + e.cost;
pre[e.v] = G[u][i];
f[e.v] = min(f[u], e.cap - e.flow);
if (!inq[e.v]) inq[e.v] = 1, q.push(e.v);
}
}
}
if (dis[T] == INF_of_int) return 0;
flow += f[T];
cost += f[T] * dis[T];
int u = T;
while (u != S) {
E[pre[u]].flow += f[T];
E[pre[u] ^ 1].flow -= f[T];
u = E[pre[u]].u;
}
return 1;
}
pi mcmf() {
int flow = 0, cost = 0;
while(spfa(flow, cost));
return pi(flow, cost);
}
};
int n, m, cnt = 0;
struct Point{
bool l, r, u, d;
int typ;
//typ = 1 one interface
//typ = 2 tow interfaces in different line
//typ = 3 tow interfaces in the same line (useless)
//typ = 4 three interfaces
//typ = 5 four interfaces (useless)
int l_id, r_id, u_id, d_id;
}g[M][M];
int mx[4] = {-1, 0, 1, 0};
int my[4] = {0, 1, 0, -1};
void insert_single_point(Point p, int typ) {
if (typ) { //black
if (p.l) Min_Cost_Max_Flow::add(Min_Cost_Max_Flow::S, p.l_id, 1, 0);
if (p.r) Min_Cost_Max_Flow::add(Min_Cost_Max_Flow::S, p.r_id, 1, 0);
if (p.u) Min_Cost_Max_Flow::add(Min_Cost_Max_Flow::S, p.u_id, 1, 0);
if (p.d) Min_Cost_Max_Flow::add(Min_Cost_Max_Flow::S, p.d_id, 1, 0);
} else { //white
if (p.l) Min_Cost_Max_Flow::add(p.l_id, Min_Cost_Max_Flow::T, 1, 0);
if (p.r) Min_Cost_Max_Flow::add(p.r_id, Min_Cost_Max_Flow::T, 1, 0);
if (p.u) Min_Cost_Max_Flow::add(p.u_id, Min_Cost_Max_Flow::T, 1, 0);
if (p.d) Min_Cost_Max_Flow::add(p.d_id, Min_Cost_Max_Flow::T, 1, 0);
}
}
void add_edge_single_point_case_1(Point p, int typ) {
if (p.l) {
if (typ) {
Min_Cost_Max_Flow::add(p.l_id, p.r_id, 1, 2);
Min_Cost_Max_Flow::add(p.l_id, p.u_id, 1, 1);
Min_Cost_Max_Flow::add(p.l_id, p.d_id, 1, 1);
} else {
Min_Cost_Max_Flow::add(p.r_id, p.l_id, 1, 2);
Min_Cost_Max_Flow::add(p.u_id, p.l_id, 1, 1);
Min_Cost_Max_Flow::add(p.d_id, p.l_id, 1, 1);
}
}
if (p.r) {
if (typ) {
Min_Cost_Max_Flow::add(p.r_id, p.l_id, 1, 2);
Min_Cost_Max_Flow::add(p.r_id, p.u_id, 1, 1);
Min_Cost_Max_Flow::add(p.r_id, p.d_id, 1, 1);
} else {
Min_Cost_Max_Flow::add(p.l_id, p.r_id, 1, 2);
Min_Cost_Max_Flow::add(p.u_id, p.r_id, 1, 1);
Min_Cost_Max_Flow::add(p.d_id, p.r_id, 1, 1);
}
}
if (p.u) {
if (typ) {
Min_Cost_Max_Flow::add(p.u_id, p.d_id, 1, 2);
Min_Cost_Max_Flow::add(p.u_id, p.l_id, 1, 1);
Min_Cost_Max_Flow::add(p.u_id, p.r_id, 1, 1);
} else {
Min_Cost_Max_Flow::add(p.d_id, p.u_id, 1, 2);
Min_Cost_Max_Flow::add(p.l_id, p.u_id, 1, 1);
Min_Cost_Max_Flow::add(p.r_id, p.u_id, 1, 1);
}
}
if (p.d) {
if (typ) {
Min_Cost_Max_Flow::add(p.d_id, p.u_id, 1, 2);
Min_Cost_Max_Flow::add(p.d_id, p.l_id, 1, 1);
Min_Cost_Max_Flow::add(p.d_id, p.r_id, 1, 1);
} else {
Min_Cost_Max_Flow::add(p.u_id, p.d_id, 1, 2);
Min_Cost_Max_Flow::add(p.l_id, p.d_id, 1, 1);
Min_Cost_Max_Flow::add(p.r_id, p.d_id, 1, 1);
}
}
}
void add_edge_single_point_case_2(Point p, int typ) {
if (p.l) {
if (typ) {
Min_Cost_Max_Flow::add(p.l_id, p.r_id, 1, 1);
} else {
Min_Cost_Max_Flow::add(p.r_id, p.l_id, 1, 1);
}
}
if (p.r) {
if (typ) {
Min_Cost_Max_Flow::add(p.r_id, p.l_id, 1, 1);
} else {
Min_Cost_Max_Flow::add(p.l_id, p.r_id, 1, 1);
}
}
if (p.u) {
if (typ) {
Min_Cost_Max_Flow::add(p.u_id, p.d_id, 1, 1);
} else {
Min_Cost_Max_Flow::add(p.d_id, p.u_id, 1, 1);
}
}
if (p.d) {
if (typ) {
Min_Cost_Max_Flow::add(p.d_id, p.u_id, 1, 1);
} else {
Min_Cost_Max_Flow::add(p.u_id, p.d_id, 1, 1);
}
}
}
void add_edge_single_point_case_3(Point p, int typ) {
if (!p.l) {
if (typ) {
Min_Cost_Max_Flow::add(p.r_id, p.l_id, 1, 2);
Min_Cost_Max_Flow::add(p.u_id, p.l_id, 1, 1);
Min_Cost_Max_Flow::add(p.d_id, p.l_id, 1, 1);
} else {
Min_Cost_Max_Flow::add(p.l_id, p.r_id, 1, 2);
Min_Cost_Max_Flow::add(p.l_id, p.u_id, 1, 1);
Min_Cost_Max_Flow::add(p.l_id, p.d_id, 1, 1);
}
}
if (!p.r) {
if (typ) {
Min_Cost_Max_Flow::add(p.l_id, p.r_id, 1, 2);
Min_Cost_Max_Flow::add(p.u_id, p.r_id, 1, 1);
Min_Cost_Max_Flow::add(p.d_id, p.r_id, 1, 1);
} else {
Min_Cost_Max_Flow::add(p.r_id, p.l_id, 1, 2);
Min_Cost_Max_Flow::add(p.r_id, p.u_id, 1, 1);
Min_Cost_Max_Flow::add(p.r_id, p.d_id, 1, 1);
}
}
if (!p.u) {
if (typ) {
Min_Cost_Max_Flow::add(p.d_id, p.u_id, 1, 2);
Min_Cost_Max_Flow::add(p.l_id, p.u_id, 1, 1);
Min_Cost_Max_Flow::add(p.r_id, p.u_id, 1, 1);
} else {
Min_Cost_Max_Flow::add(p.u_id, p.d_id, 1, 2);
Min_Cost_Max_Flow::add(p.u_id, p.l_id, 1, 1);
Min_Cost_Max_Flow::add(p.u_id, p.r_id, 1, 1);
}
}
if (!p.d) {
if (typ) {
Min_Cost_Max_Flow::add(p.u_id, p.d_id, 1, 2);
Min_Cost_Max_Flow::add(p.l_id, p.d_id, 1, 1);
Min_Cost_Max_Flow::add(p.r_id, p.d_id, 1, 1);
} else {
Min_Cost_Max_Flow::add(p.d_id, p.u_id, 1, 2);
Min_Cost_Max_Flow::add(p.d_id, p.l_id, 1, 1);
Min_Cost_Max_Flow::add(p.d_id, p.r_id, 1, 1);
}
}
}
void add_edge_between_points(Point a, Point b, int dir) {
if (dir == 0) Min_Cost_Max_Flow::add(a.u_id, b.d_id, 1, 0);
if (dir == 1) Min_Cost_Max_Flow::add(a.r_id, b.l_id, 1, 0);
if (dir == 2) Min_Cost_Max_Flow::add(a.d_id, b.u_id, 1, 0);
if (dir == 3) Min_Cost_Max_Flow::add(a.l_id, b.r_id, 1, 0);
}
int main() {
#ifdef dream_maker
freopen("input.txt", "r", stdin);
#endif
Read(n);Read(m);
int sum = 0;
Min_Cost_Max_Flow::S = 0;
Min_Cost_Max_Flow::T = n * m * 4 + 1;
fu(i, 1, n) {
fu(j, 1, m) {
int w;Read(w);
g[i][j].u = (w & (1 << 0)); g[i][j].u_id = ++cnt;
g[i][j].r = (w & (1 << 1)); g[i][j].r_id = ++cnt;
g[i][j].d = (w & (1 << 2)); g[i][j].d_id = ++cnt;
g[i][j].l = (w & (1 << 3)); g[i][j].l_id = ++cnt;
int num = g[i][j].u + g[i][j].r + g[i][j].d + g[i][j].l;
sum += num;
if (num == 1) {
add_edge_single_point_case_1(g[i][j], (i + j) & 1);
} else if (num == 2) {
if ((!g[i][j].u || !g[i][j].d) && (!g[i][j].l || !g[i][j].r))
add_edge_single_point_case_2(g[i][j], (i + j) & 1);
} else if (num == 3) {
add_edge_single_point_case_3(g[i][j], (i + j) & 1);
}
insert_single_point(g[i][j], (i + j) & 1);
}
}
fu(i, 1, n) {
fu(j, 1, m) {
if ((i + j) & 1) {
fu(k, 0, 3) {
int ni = i + mx[k], nj = j + my[k];
if (ni < 1 || ni > n || nj < 1 || nj > m) continue;
add_edge_between_points(g[i][j], g[ni][nj], k);
}
}
}
}
pi res = Min_Cost_Max_Flow::mcmf();
if (res.first * 2 != sum) Write(-1);
else Write(res.second);
return 0;
}