zqs`s blog

有朋自远方来，虽远必诛

题解 【P4003 无限之环】

发表于 分类于 Valine：

就我的建图这么清奇？

由于这是一个网格图而且还有各种奇怪的形状和限制以及奇怪的数据范围，可以往网络流考虑。

如果一个图不漏水，那么每个格子的度数必定是这个格子的水管的分叉数。

对网格图进行黑白染色，则问题变为从黑点向白点提供一些度数，使得源点向黑点连的边和白点向汇点连的边均满流。

题目要求旋转次数最少，考虑费用流。

首先每个点拆成五个点，分别表示它往上下左右方向的连边和它本身。

以下只讨论黑格子。

从 $s$ 向这个格子本身的点连边，容量为这个格子水管分叉数（设为 $x$），费用为 $0$。表示不管怎么旋转它都会连接 $x$ 个方向。

格子按照分叉数和是否为直线分为以下 $5$ 种情况：

1分叉（圆圈形）

没什么好说的，向上下左右各连一条容量 $1$， 费用为原方向旋转到这个方向的旋转次数即可。

2分叉（直线形）

这种情况也很简单，直线不能转，根据直线是横着的还是竖着的向上下各连容量 $1$ 费用 $0$ 的边或向左右连边。

2分叉（转弯形）

这种情况必须横方向有一个水管，竖方向有一个水管，所以再额外建立两个点表示横方向和竖方向，然后向横点和竖点各连一条容量 $1$ 费用 $0$ 的边。

再从横点向上下连边，竖点向左右连边，容量均为 $1$，费用为开始水管的方向是否朝向了这里，如果是则为 $0$，否则为 $1$。

3分叉（T字形）

这个情况看起来很难搞……

没事大不了我针对4种T形各拆一个点就好了

但这样做显然是不行的，因为流量会到处跑，而且码量比较劝退。

那我们就直接按照 $1$ 分叉的连边改一改费用！

假设是这种朝下的T形：

设向上面连的边费用为 $a_1$，向左连的边费用为 $a_2$，向右连的边费用为 $a_3$，向下为 $a_4$。

那么根据实际的旋转次数，我们希望这些费用满足以下条件：

解一下方程发现 $a_1=4/3,a_2=a_3=1/3,a_4=-2/3$。

这里有一个技巧可以避免小数费用流带来的常数，因为整个图中只有这一个地方有分数的费用并且分母都是 $3$，所以只要把所有边的费用乘 $3$，输出的时候除回来就好了。

4分叉（十字形）

如果看懂了上面的连边这里就不用我说了吧（

向上下左右各连一条容量 $1$ 费用 $0$ 的边即可。

白点就是把上面的连边全部反过来了，为了避免复制粘贴使得代码看起来很长我用了rev变量标记。

然后有个相邻点之间的连边，比如 $(x,y)$ 的黑点的上方连 $(x-1,y)$ 的白点的下方等等，很简单就不赘述了。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <cstdio>
#include <queue>
#include <cstring>
#define U 0
#define D 1
#define L 2
#define R 3
#define UD 4
#define LR 5

const int INF = 1e9;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
inline int min(const int x, const int y) {return x < y ? x : y;}
struct Edge {
	int to, cap, cost, nxt;
} e[10000005];
int head[100005], cur[100005], dis[100005];
int tot = 1, s, t, Maxflow, Mincost;
bool vis[100005], mark[100005];
std::queue<int> Q;
bool rev;
inline void AddEdge(int u, int v, int cap, int cost, bool mul = true) {
	if (rev) u ^= v ^= u ^= v;
	if (mul) cost *= 3;
	e[++ tot].to = v, e[tot].nxt = head[u], head[u] = tot;
	e[tot].cap = cap, e[tot].cost = cost;
	e[++ tot].to = u, e[tot].nxt = head[v], head[v] = tot;
	e[tot].cap = 0, e[tot].cost = -cost;
}
bool SPFA() {
	memcpy(cur, head, sizeof cur);
	memset(vis, 0, sizeof vis);
	memset(dis, 0x3f, sizeof dis);
	memset(mark, 0, sizeof mark);
	Q.push(s);
	dis[s] = 0;
	while (Q.size()) {
		int u(Q.front());
		Q.pop();
		mark[u] = false;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			if (e[i].cap && dis[u] + e[i].cost < dis[v]) {
				dis[v] = dis[u] + e[i].cost;
				if (!mark[v]) Q.push(v), mark[v] = true;
			}
		}
	}
	return dis[t] < INF;
}

int dfs(int u, int flow) {
	if (u == t) return flow;
	vis[u] = true;
	int used = 0, tmp;
	for (int i = cur[u]; i && used <= flow; i = e[i].nxt) {
		cur[u] = i;
		if (e[i].cap && dis[u] + e[i].cost == dis[e[i].to]) {
			int v = e[i].to;
			if (!vis[v] && (tmp = dfs(v, min(flow - used, e[i].cap))))
				used += tmp, e[i].cap -= tmp, e[i ^ 1].cap += tmp;
		}
	}
	return used;
}

void Dinic() {
	int flow = 0;
	while (SPFA()) Maxflow += (flow = dfs(s, INF)), Mincost += flow * dis[t];
}

int n, m, id[2005][6], a[2005], cnt;
inline int pos(int i, int j) {return (i - 1) * m + j;}

int main() {
	int sum1 = 0, sum2 = 0;
	scanf("%d%d", &n, &m);
	s = 0, t = 20000, cnt = n * m;
	for (int i = 1; i <= n; ++ i)
	for (int j = 1; j <= m; ++ j) {
		int p = pos(i, j);
		scanf("%d", a + p);
		if (!a[p]) continue;
		int len = 0;
		for (int k = 0; k <= 3; ++ k)
			if (a[p] & 1 << k) ++ len;
		rev = i + j & 1;
		if (!rev) AddEdge(s, p, len, 0), sum1 += len;
		else AddEdge(t, p, len, 0), sum2 += len;
		switch (a[p]) {
			case 5:
				AddEdge(p, id[p][U] = ++ cnt, 1, 0);
				AddEdge(p, id[p][D] = ++ cnt, 1, 0);
				break;
			case 10:
				AddEdge(p, id[p][L] = ++ cnt, 1, 0);
				AddEdge(p, id[p][R] = ++ cnt, 1, 0);
				break;
			case 1:
			case 2:
			case 4:
			case 8:
				AddEdge(p, id[p][U] = ++ cnt, 1, (a[p] == 1 ? 0 : (a[p] == 4 ? 2 : 1)));
				AddEdge(p, id[p][D] = ++ cnt, 1, (a[p] == 4 ? 0 : (a[p] == 1 ? 2 : 1)));
				AddEdge(p, id[p][L] = ++ cnt, 1, (a[p] == 8 ? 0 : (a[p] == 2 ? 2 : 1)));
				AddEdge(p, id[p][R] = ++ cnt, 1, (a[p] == 2 ? 0 : (a[p] == 8 ? 2 : 1)));
				break;
			case 3:
			case 6:
			case 9:
			case 12:
				AddEdge(p, id[p][UD] = ++ cnt, 1, 0);
				AddEdge(p, id[p][LR] = ++ cnt, 1, 0);
				AddEdge(id[p][UD], id[p][U] = ++ cnt, 1, !((bool)(a[p] & 1)));
				AddEdge(id[p][UD], id[p][D] = ++ cnt, 1, !((bool)(a[p] & 4)));
				AddEdge(id[p][LR], id[p][L] = ++ cnt, 1, !((bool)(a[p] & 8)));
				AddEdge(id[p][LR], id[p][R] = ++ cnt, 1, !((bool)(a[p] & 2)));
				break;
			case 7:
			case 11:
			case 13:
			case 14:
				AddEdge(p, id[p][U] = ++ cnt, 1, (a[p] == 11 ? -2 : (a[p] == 14 ? 4 : 1)), 0);
				AddEdge(p, id[p][D] = ++ cnt, 1, (a[p] == 14 ? -2 : (a[p] == 11 ? 4 : 1)), 0);
				AddEdge(p, id[p][L] = ++ cnt, 1, (a[p] == 13 ? -2 : (a[p] == 7 ? 4 : 1)), 0);
				AddEdge(p, id[p][R] = ++ cnt, 1, (a[p] == 7 ? -2 : (a[p] == 13 ? 4 : 1)), 0);
				break;
			default:
				AddEdge(p, id[p][U] = ++ cnt, 1, 0);
				AddEdge(p, id[p][D] = ++ cnt, 1, 0);
				AddEdge(p, id[p][L] = ++ cnt, 1, 0);
				AddEdge(p, id[p][R] = ++ cnt, 1, 0);
		}
	}
	rev = false;
	for (int i = 1; i <= n; ++ i)
	for (int j = 1; j <= m; ++ j)
		if (!(i + j & 1) && a[pos(i, j)]) {
			int p = pos(i, j);
			for (int k = 0; k <= 3; ++ k) {
				int x = i + dx[k], y = j + dy[k];
				if (x < 1 || y < 1 || n < x || m < y || !a[pos(x, y)]) continue;
				int p2 = pos(x, y);
				if (id[p][U] && id[p2][D] && k == 0) AddEdge(id[p][U], id[p2][D], 1, 0);
				if (id[p][D] && id[p2][U] && k == 1) AddEdge(id[p][D], id[p2][U], 1, 0);
				if (id[p][L] && id[p2][R] && k == 2) AddEdge(id[p][L], id[p2][R], 1, 0);
				if (id[p][R] && id[p2][L] && k == 3) AddEdge(id[p][R], id[p2][L], 1, 0);
			}
		}
	Dinic();
	printf("%d", Maxflow == sum1 && sum1 == sum2 ? Mincost / 3 : -1);
}
-------------本文结束感谢您的阅读-------------