AtCoder Regular Contest 089: E - GraphXY
すぐに思い付いたのに頂点番号に$+1$するのを忘れてWAをたくさん生やした。Pythonで書き始めて途中でC++に切り替えたときに混入したバグだった。
問題は好き。
solution
$S \overset{X}{\to} \cdot \overset{X}{\to} \cdot \overset{X}{\to} \dots$ のような鎖と $\dots \overset{Y}{\to} \cdot \overset{Y}{\to} \cdot \overset{Y}{\to} T$ のような鎖を用意し、これらの点の間を適当に繋ぐ。$O(AB \cdot (\max d_{x, y})^2)$。
まず$S \to T$のpathを考えたときその重みは$ax + by + c$の形をしている。 それぞれの対$(x, y)$について$ax + by + c = d_{x, y}$となるような$(a, b, c)$を見つけてそのようなpathを作っていけばよさそう。 しかし別の$(x’, y’)$の制約を壊してはならず、また使用する頂点数が$300$以下でなければならない。 後者は先に示したような鎖を使って$a, b$を設定する部分を全てのpathで共有しそれらを繋ぐ中央の辺で$c$を設定することで解決できる。 前者は$(x, y)$から$(a, b, c)$を決定するのでなく$(a, b, c)$で可能なものを総当たりすることで解決できる。 $(a, b)$を固定すれば使う$c$はひとつたけでよく、多重辺がだめなので辺を共有するならばむしろひとつでなければならないことに注意。
implementation
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
using namespace std;
template <class T> inline void chmax(T & a, T const & b) { a = max(a, b); }
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }
int main() {
// input
int a, b; cin >> a >> b;
auto d = vectors(a, b, int());
REP (x, a) REP (y, b) cin >> d[x][y];
// solve
constexpr int n = 300;
constexpr int max_d = 100;
constexpr int max_c = 100;
// // prepare the structure
vector<tuple<int, int, char> > char_edge;
vector<int> xs(max_d + 1);
vector<int> ys(max_d + 1);
xs[0] = 0;
ys[0] = n - 1;
REP (i, max_d) {
xs[i + 1] = xs[i] + 1;
ys[i + 1] = ys[i] - 1;
char_edge.emplace_back(xs[i], xs[i + 1], 'X');
char_edge.emplace_back(ys[i + 1], ys[i], 'Y');
}
// // construct the required graph
auto used = vectors(a, b, false);
vector<tuple<int, int, int> > int_edge;
REP (i, max_d + 1) REP (j, max_d + 1) if (i + j <= max_d) {
int c = 0;
REP (x, a) REP (y, b) {
int f = i * (x + 1) + j * (y + 1);
chmax(c, d[x][y] - f);
}
if (c > max_c) continue;
int_edge.emplace_back(xs[i], ys[j], c);
REP (x, a) REP (y, b) {
int f = i * (x + 1) + j * (y + 1);
assert (d[x][y] <= f + c);
if (f + c == d[x][y]) {
used[x][y] = true;
}
}
}
// // check the result
bool possible = true;
REP (x, a) REP (y, b) {
if (not used[x][y]) {
possible = false;
}
}
// output
cout << (possible ? "Possible" : "Impossible") << endl;
if (possible) {
int m = int_edge.size() + char_edge.size();
cout << n << ' ' << m << endl;
for (auto e : char_edge) {
cout << get<0>(e) + 1 << ' ' << get<1>(e) + 1 << ' ' << get<2>(e) << endl;
}
for (auto e : int_edge) {
cout << get<0>(e) + 1 << ' ' << get<1>(e) + 1 << ' ' << get<2>(e) << endl;
}
int s = xs[0];
int t = ys[0];
cout << s + 1 << ' ' << t + 1 << endl;
}
return 0;
}