[Luogu P4003] [BZOJ 5120] [THU集训] 无限之环
洛谷传送门
BZOJ传送门
题目描述
曾经有一款流行的游戏,叫做 Infinity Loop,先来简单的介绍一下这个游戏:
游戏在一个 的网格状棋盘上进行,其中有些小方格中会有水管,水管可能在
格某些方向的边界的中点有接口,所有水管的粗细都相同,所以如果两个相邻方格的
共边界的中点都有接头,那么可以看作这两个接头互相连接。水管有以下 种形状:
游戏开始时,棋盘中水管可能存在漏水的地方。形式化地:如果存在某个接头,没有和其它接头相连接,那么它就是一个漏水的地方。
玩家可以进行一种操作:选定一个含有非直线型水管的方格,将其中的水管绕方格中心顺时针或逆时针旋转 度。
直线型水管是指左图里中间一行的两种水管。现给出一个初始局面,请问最少进行多少次操作可以使棋盘上不存在漏水的地方。
输入输出格式
输入格式:
从文件 infinityloop.in 中读入数据。
第一行两个正整数 , ,代表网格的大小。
接下来 行每行 个数,每个数是 中的一个,你可以将其看作一个 位的
二进制数,从低到高每一位分别代表初始局面中这个格子上、右、下、左方向上是否有水管接头。
特别地,如果这个数是 ,则意味着这个位置没有水管。
比如 $3(0011(2)) $代表上和右有接头,也就是一个 型,而 代表下和左
有接头,也就是将 型旋转 度。
输出格式:
输出到文件 infinityloop.out 中。
输出共一行,表示最少操作次数。如果无法达成目标,输出.
输入输出样例
输入样例#1:
2 3
3 14 12
3 11 12
输出样例#1:
2
输入样例#2:
3 2
1 8
5 10
2 4
输出样例#2:
-1
输入样例#3:
3 3
9 11 3
13 15 7
12 14 6
输出样例#3:
16
说明
【样例 1 解释】
样例 1 棋盘如下
旋转方法很显然,先将左上角虚线方格内的水管顺时针转 90 度
然后右下角虚线方格内的水管逆时针旋转 90 度,这样就使得水管封闭了
【样例 2 解释】
样例 2 为题目描述中的第一张图片,无法达成目标。
【样例 3 解释】
样例 3 为题目描述中的第二张图片,将除了中心方格以外的每个方格内的水管都转 180 度即可。
解题分析
费用流神题啊(听说轮廓线吊打费用流orz)QAQ…
考虑到可能拼好之后会有很多连通的环,不利于确定源汇, 我们不妨黑白染色, 强制流向相邻的点。 很显然, 我们需要拆成5个点, 分别表示中点, 向上方向, 向下方向, 向左方向, 向右方向。 现在我们会做没有旋转操作的了, 我们可以根据要求从向中点或从中点向连流量为水管支线数量的边, 再从中点依次向对应方向或从对应方向向中点连流量为, 费用为的边。 最后我们看是否流量达到所有水管支线数量即可。
考虑如何将旋转的情况考虑进去。先来看正形的情况, 逆时针旋转90°其实等同于将向右的水管接到向左的水管, 因此我们直接从向右方向的点连向向左方向的点连一条流量为, 花费为的边, 从向上方向向向下方向的点连一条流量为, 花费为的边。 丄形的同理。
然后我们发现, 题目中规定直线型的水管不能旋转的原因就在于其不能通过这样增加花费的方式得到旋转后的结果。
代码如下:
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <cmath>
#include <queue>
#define R register
#define IN inline
#define W while
#define gc getchar()
#define INF 1e8
#define get(i, j) (((i - 1) * m + j) * 5)
#define DEBUG(i, j, k, l) printf("%d %d %d %d\n", i, j, k, l)
#define MX 10050
#define m(i, j) (get(i, j) + 1)
#define u(i, j) (get(i, j) + 2)
#define d(i, j) (get(i, j) + 3)
#define l(i, j) (get(i, j) + 4)
#define r(i, j) (get(i, j) + 5)
template <class C> IN C max(C a, C b) {return a > b ? a : b;}
template <class C> IN C min(C a, C b) {return a < b ? a : b;}
template <class C>
IN void in(C &x)
{
x = 0; R char c = gc;
for (; !isdigit(c); c = gc);
for (; isdigit(c); c = gc)
x = (x << 1) + (x << 3) + c - 48;
}
int n, m, sum, S, T, cnt, flow, ans;
int head[MX], pre[MX], dis[MX], del[MX];
int mp[2050][2050];
bool inq[MX];
struct Edge {int to, fl, len, nex;} edge[200500];
IN void add(R int from, R int to, R int fl, R int cst, R bool inv)
{//如果中点连向T, 就把方向反过来连
if (inv) std::swap(from, to);
edge[++cnt] = {to, fl, cst, head[from]}, head[from] = cnt;
edge[++cnt] = {from, 0, -cst, head[to]}, head[to] = cnt;
}
namespace MCMF
{
std::queue <int> q;
IN bool SPFA()
{
std::memset(dis, 63, sizeof(dis));
dis[S] = 0; del[S] = INF; q.push(S); R int now;
W (!q.empty())
{
now = q.front(); q.pop();
for (R int i = head[now]; ~i; i = edge[i].nex)
{
if (dis[edge[i].to] > dis[now] + edge[i].len && edge[i].fl)
{
dis[edge[i].to] = dis[now] + edge[i].len;
del[edge[i].to] = min(del[now], edge[i].fl);
pre[edge[i].to] = i;
if (!inq[edge[i].to]) inq[edge[i].to] = true, q.push(edge[i].to);
}
}
inq[now] = false;
}
return dis[T] ^ dis[0];
}
IN void update()
{
R int now = T, pr;
flow += del[T], ans += del[T] * dis[T];
W (now ^ S)
{
pr = pre[now];
edge[pr].fl -= del[T], edge[pr ^ 1].fl += del[T];
now = edge[pr ^ 1].to;
}
}
IN void solve()
{
W (SPFA()) update();
printf("%d", flow * 2 == sum ? ans : -1);
}
}
/*
0001 up
0010 rig
0100 down
1000 lef
1 mid
2 up
3 down
4 lef
5 rig
*/
int main(void)
{
int typ, ct;
in(n), in(m); S = n * m * 5 + 10, T = n * m * 5 + 11;
std::memset(head, cnt = -1, sizeof(head));
for (R int i = 1; i <= n; ++i) for (R int j = 1; j <= m; ++j) in(mp[i][j]);
for (R int i = 1; i <= n; ++i) for (R int j = 1; j <= m; ++j)
{
typ = (i + j) & 1; ct = __builtin_popcount(mp[i][j]);
if (!mp[i][j]) continue;
if (typ) add(m(i, j), T, ct, 0, 0), sum += ct;
else
{
add(S, m(i, j), ct, 0, 0), sum += ct;
if (mp[i - 1][j]) add(u(i, j), d(i - 1, j), 1, 0, 0);
if (mp[i + 1][j]) add(d(i, j), u(i + 1, j), 1, 0, 0);
if (mp[i][j - 1]) add(l(i, j), r(i, j - 1), 1, 0, 0);
if (mp[i][j + 1]) add(r(i, j), l(i, j + 1), 1, 0, 0);
}
switch(mp[i][j])
{
case 1://u
{
add(m(i, j), u(i, j), 1, 0, typ);
add(u(i, j), l(i, j), 1, 1, typ);
add(u(i, j), r(i, j), 1, 1, typ);
add(u(i, j), d(i, j), 1, 2, typ);
break;
}
case 2://r
{
add(m(i, j), r(i, j), 1, 0, typ);
add(r(i, j), u(i, j), 1, 1, typ);
add(r(i, j), d(i, j), 1, 1, typ);
add(r(i, j), l(i, j), 1, 2, typ);
break;
}
case 3://ur
{
add(m(i, j), r(i, j), 1, 0, typ);
add(m(i, j), u(i, j), 1, 0, typ);
add(u(i, j), d(i, j), 1, 1, typ);
add(r(i, j), l(i, j), 1, 1, typ);
break;
}
case 4://d
{
add(m(i, j), d(i, j), 1, 0, typ);
add(d(i, j), l(i, j), 1, 1, typ);
add(d(i, j), r(i, j), 1, 1, typ);
add(d(i, j), u(i, j), 1, 2, typ);
break;
}
case 5://ud, cannot rotate
{
add(m(i, j), u(i, j), 1, 0, typ);
add(m(i, j), d(i, j), 1, 0, typ);
break;
}
case 6://dr
{
add(m(i, j), r(i, j), 1, 0, typ);
add(m(i, j), d(i, j), 1, 0, typ);
add(r(i, j), l(i, j), 1, 1, typ);
add(d(i, j), u(i, j), 1, 1, typ);
break;
}
case 7://urd
{
add(m(i, j), u(i, j), 1, 0, typ);
add(m(i, j), r(i, j), 1, 0, typ);
add(m(i, j), d(i, j), 1, 0, typ);
add(u(i, j), l(i, j), 1, 1, typ);
add(d(i, j), l(i, j), 1, 1, typ);
add(r(i, j), l(i, j), 1, 2, typ);
break;
}
case 8://l
{
add(m(i, j), l(i, j), 1, 0, typ);
add(l(i, j), u(i, j), 1, 1, typ);
add(l(i, j), d(i, j), 1, 1, typ);
add(l(i, j), r(i, j), 1, 2, typ);
break;
}
case 9://ul
{
add(m(i, j), u(i, j), 1, 0, typ);
add(m(i, j), l(i, j), 1, 0, typ);
add(u(i, j), d(i, j), 1, 1, typ);
add(l(i, j), r(i, j), 1, 1, typ);
break;
}
case 10://lr, cannot rotate
{
add(m(i, j), l(i, j), 1, 0, typ);
add(m(i, j), r(i, j), 1, 0, typ);
break;
}
case 11://lru
{
add(m(i, j), l(i, j), 1, 0, typ);
add(m(i, j), u(i, j), 1, 0, typ);
add(m(i, j), r(i, j), 1, 0, typ);
add(l(i, j), d(i, j), 1, 1, typ);
add(r(i, j), d(i, j), 1, 1, typ);
add(u(i, j), d(i, j), 1, 2, typ);
break;
}
case 12://ld
{
add(m(i, j), l(i, j), 1, 0, typ);
add(m(i, j), d(i, j), 1, 0, typ);
add(l(i, j), r(i, j), 1, 1, typ);
add(d(i, j), u(i, j), 1, 1, typ);
break;
}
case 13://udl
{
add(m(i, j), l(i, j), 1, 0, typ);
add(m(i, j), u(i, j), 1, 0, typ);
add(m(i, j), d(i, j), 1, 0, typ);
add(u(i, j), r(i, j), 1, 1, typ);
add(d(i, j), r(i, j), 1, 1, typ);
add(l(i, j), r(i, j), 1, 2, typ);
break;
}
case 14://lrd
{
add(m(i, j), l(i, j), 1, 0, typ);
add(m(i, j), r(i, j), 1, 0, typ);
add(m(i, j), d(i, j), 1, 0, typ);
add(l(i, j), u(i, j), 1, 1, typ);
add(r(i, j), u(i, j), 1, 1, typ);
add(d(i, j), u(i, j), 1, 2, typ);
break;
}
case 15:
{
add(m(i, j), l(i, j), 1, 0, typ);
add(m(i, j), r(i, j), 1, 0, typ);
add(m(i, j), u(i, j), 1, 0, typ);
add(m(i, j), d(i, j), 1, 0, typ);
break;
}
}
}
MCMF::solve();
}