けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Codeforces Round #617 (Div. 3) F. Berland Beauty (R2100)

面白かった!!!

問題へのリンク

問題概要

 N 頂点の木が与えられる。木の各辺に対して、以下の条件を満たすように 1 以上 1000000 以下の整数値を割り振りたい。

  • 条件は  M 個ある
  •  i 番目の条件は、2 頂点  a_{i}, b_{i} と整数値  g_{i} が指定されて、 a_{i}, b_{i} を結ぶパス上の辺の値の最小値が  g_{i} に一致する

この条件を満たすような整数値の割り振り方を 1 つ構築せよ。不可能な場合は -1 と出力せよ。

制約

  •  N, M \le 5000

考えたこと

まずはあれこれ手を動かしてみよう。最初に気になったのは「どういう場合が不可能なんだろう...」ということだった。

不可能な場合は比較的すぐに見えてきた。たとえば

  • パス 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 した。整合しなかったらダメ。

計算量は、 O(NM)

#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();
    }
}