好奇特的题。
考虑显式建图,那么这是一个 \(9\) 个结点,\(12\) 条边的图,需要找到一条回路使得第 \(i\) 个点被经过 \(a_i\) 次。
首先会有一个基本思路:先求出每条边经过的次数,然后每条边复制这么多次即可直接构造欧拉回路。其中每条边经过次数的限制就是,每个点连出去的边,经过次数之和等于 \(2 \times a_i\),并且去掉没经过的边,图仍然连通。
考虑直接暴力枚举图的一棵生成树,钦定这些边至少被经过 \(1\) 次,然后在这个二分图上跑最大流,判断最大流是否为 \(\sum a_i\) 即可得知是否合法。
还有一种做法是,列出 \(9\) 个 \(12\) 元一次方程组,暴力枚举自由元的值判断。
code
// Problem: H - Eat Them All
// Contest: AtCoder - KEYENCE Programming Contest 2021 (AtCoder Beginner Contest 227)
// URL: https://atcoder.jp/contests/abc227/tasks/abc227_h
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
int a[99], b[99], head[99], len, S, T, ntot, fa[99], id[99];
struct edge {
int to, next, cap, flow;
} edges[9999];
inline void add_edge(int u, int v, int c, int f) {
edges[++len].to = v;
edges[len].next = head[u];
edges[len].cap = c;
edges[len].flow = f;
head[u] = len;
}
struct Dinic {
int d[99], cur[99];
bool vis[99];
inline void add(int u, int v, int c) {
add_edge(u, v, c, 0);
add_edge(v, u, 0, 0);
}
inline bool bfs() {
queue<int> q;
for (int i = 0; i <= ntot; ++i) {
vis[i] = 0;
d[i] = -1;
}
q.push(S);
vis[S] = 1;
d[S] = 0;
while (q.size()) {
int u = q.front();
q.pop();
for (int i = head[u]; i; i = edges[i].next) {
edge &e = edges[i];
if (!vis[e.to] && e.cap > e.flow) {
vis[e.to] = 1;
d[e.to] = d[u] + 1;
q.push(e.to);
}
}
}
return vis[T];
}
int dfs(int u, int a) {
if (u == T || !a) {
return a;
}
int flow = 0, f;
for (int &i = cur[u]; i; i = edges[i].next) {
edge &e = edges[i];
if (d[e.to] == d[u] + 1 && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) {
e.flow += f;
edges[i ^ 1].flow -= f;
flow += f;
a -= f;
if (!a) {
break;
}
}
}
return flow;
}
inline int solve() {
int flow = 0;
while (bfs()) {
for (int i = 0; i <= ntot; ++i) {
cur[i] = head[i];
}
flow += dfs(S, inf);
}
return flow;
}
} solver;
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
inline bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
fa[x] = y;
return 1;
} else {
return 0;
}
}
int p[9999], tot;
vector<pii> G[99];
bool vis[9999];
void dfs(int u) {
for (pii p : G[u]) {
int v = p.fst, id = p.scd;
if (!vis[id]) {
vis[id] = 1;
dfs(v);
}
}
p[++tot] = u;
}
void solve() {
int s0 = 0, s1 = 0;
for (int i = 0; i < 3; ++i) {
for (int j = 0, x; j < 3; ++j) {
scanf("%d", &x);
a[i * 3 + j] = x * 2;
if ((i + j) & 1) {
s1 += a[i * 3 + j];
} else {
s0 += a[i * 3 + j];
}
}
}
if (s0 != s1) {
puts("NO");
return;
}
vector<pii> E;
E.pb(0, 1);
E.pb(1, 2);
E.pb(3, 4);
E.pb(4, 5);
E.pb(6, 7);
E.pb(7, 8);
E.pb(0, 3);
E.pb(3, 6);
E.pb(1, 4);
E.pb(4, 7);
E.pb(2, 5);
E.pb(5, 8);
for (int S = 1; S < (1 << 12); ++S) {
if (__builtin_popcount(S) != 8) {
continue;
}
for (int i = 0; i < 9; ++i) {
fa[i] = i;
b[i] = a[i];
vector<pii>().swap(G[i]);
}
bool flag = 0;
for (int i = 0; i < 12; ++i) {
if ((~S) & (1 << i)) {
continue;
}
if (!merge(E[i].fst, E[i].scd)) {
flag = 1;
break;
}
--b[E[i].fst];
--b[E[i].scd];
}
for (int i = 0; i < 9; ++i) {
if (b[i] < 0) {
flag = 1;
break;
}
}
if (flag) {
continue;
}
len = 1;
mems(head, 0);
ntot = 8;
::S = ++ntot;
T = ++ntot;
for (int i = 0; i < 12; ++i) {
int u = E[i].fst, v = E[i].scd;
if (u & 1) {
solver.add(v, u, inf);
} else {
solver.add(u, v, inf);
}
id[i] = len - 1;
}
for (int i = 0; i < 9; ++i) {
if (i & 1) {
solver.add(i, T, b[i]);
} else {
solver.add(::S, i, b[i]);
}
}
int flow = solver.solve();
if (flow + 8 != s0) {
continue;
}
mems(vis, 0);
int tt = 0;
for (int i = 0; i < 12; ++i) {
int k = ((S >> i) & 1) + edges[id[i]].flow, u = E[i].fst, v = E[i].scd;
for (int j = 0; j < k; ++j) {
G[u].pb(v, ++tt);
G[v].pb(u, tt);
}
}
dfs(0);
reverse(p + 1, p + tot + 1);
for (int i = 1; i < tot; ++i) {
if (p[i + 1] == p[i] + 1) {
putchar('R');
} else if (p[i + 1] == p[i] - 1) {
putchar('L');
} else if (p[i + 1] == p[i] + 3) {
putchar('D');
} else {
putchar('U');
}
}
return;
}
puts("NO");
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Beginner AtCoder Contest Them 227beginner atcoder contest them contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 310