面白かった!!!
問題概要
頂点の木が与えられる。木の各辺に対して、以下の条件を満たすように 1 以上 1000000 以下の整数値を割り振りたい。
- 条件は 個ある
- 番目の条件は、2 頂点 と整数値 が指定されて、 を結ぶパス上の辺の値の最小値が に一致する
この条件を満たすような整数値の割り振り方を 1 つ構築せよ。不可能な場合は -1 と出力せよ。
制約
考えたこと
まずはあれこれ手を動かしてみよう。最初に気になったのは「どういう場合が不可能なんだろう...」ということだった。
不可能な場合は比較的すぐに見えてきた。たとえば
- パス p が、パス q に包含されていて
- パス p の最小値が、パス q の最小値よりも小さい
という状態だったら不可能だ。たとえば
- パス p:辺 (1, 2) と辺 (2, 3) のみで値は 3
- パス q:辺 (1, 2) と辺 (2, 3) と辺 (3, 4) で値は 5
という状況だったとき、パス q のうち、p の部分ですでに 3 以下になることが確定しているため、ダメだ。
しかし、そうでなければ実は可能だ。なぜなら、パス p がパス q からはみ出していれば、はみ出した部分にパス p の最小値を割り振ればよいからだ。むしろ p と q のかぶった部分については q 側に合わせればよい。
そして「p と q で被ったときは、q 側に合わせる」という部分から、ハッとなった。問題の見方を変えてみよう。
見方を変える
パス視点ではなく、各辺視点で物事を考えてみる。辺 e が絡む条件が複数あるとき、辺 e はどういう値にすればよいであろうか。たとえば
- 辺 e があるパス p に含まれていて、パス p の最小値は 3
- 辺 e があるパス q に含まれていて、パス q の最小値は 4
という状況だったら、辺 e の値は 4 にしておけばよい (3 にしてはいけない)。というわけでこの問題は
- 各辺について、それを含むパスの最小値の最大値を割り振る
という風にする。どのパスにも含まれない辺の重みはとりあえず 100000 とかにして差し支えない。そしてこうして求めたものが整合するかを check した。整合しなかったらダメ。
計算量は、。
#include <bits/stdc++.h> using namespace std; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using Edge = pair<int,int>; using Graph = vector<vector<Edge> >; const int INF = 1000000; int N, M; Graph G; bool rec(int v, int p, int target, vector<int> &path) { if (v == target) { path.clear(); return true; } for (auto e : G[v]) { if (e.first == p) continue; if (rec(e.first, v, target, path)) { path.push_back(e.second); return true; } } return false; } void solve() { cin >> M; vector<int> res(N-1, 0); vector<vector<int>> paths(M); vector<int> g(M); for (int i = 0; i < M; ++i) { int a, b; cin >> a >> b >> g[i]; --a, --b; rec(a, -1, b, paths[i]); for (auto e : paths[i]) chmax(res[e], g[i]); } for (int i = 0; i < res.size(); ++i) if (res[i] == 0) res[i] = INF; bool ok = true; for (int i = 0; i < M; ++i) { int tmp = INF; for (auto e : paths[i]) chmin(tmp, res[e]); if (tmp != g[i]) ok = false; } if (ok) { for (int i = 0; i < N-1; ++i) { if (i) printf(" "); printf("%d", res[i]); } printf("\n"); } else printf("-1\n"); } int main() { while (scanf("%d", &N) != EOF) { G.assign(N, vector<Edge>()); for (int i = 0; i < N-1; ++i) { int u, v; scanf("%d %d", &u, &v); --u, --v; G[u].emplace_back(v, i); G[v].emplace_back(u, i); } solve(); } }