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

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

AtCoder ABC 373 D - Hidden Weights (2Q, 茶色, 400 点)

AtCoder AtCoder400点 ABC-D 茶色diff NoviSteps2Q DFS 【問題集】DFS・BFSのステップアップ BFS 差分制約系 重み付きUnion-Find グラフ 二部グラフ判定 グラフ探索:頂点の値を求めていく Greedy:端から順に決まっていく

二部グラフ判定を書いたことがあれば、その要領で解ける！

問題概要

頂点数 N、辺数 M の重み付き有向グラフが与えられる。各頂点 v に値 x_{v} を書き込む方法であって、どの辺 e = (u, v; w) に対しても

x_{v} - x_{u} = w

を満たすようなものを 1 つ求めよ (そのようなものが存在することは保証される)。

制約

  • 2 \le N \le 2 \times 10^{5}
  • 1 \le M \le 2 \times 10^{5}

考えたこと

二部グラフ判定と同様の DFS で解ける。グラフの各連結成分について、1 つの頂点の値を決めると、連結成分内の残りの頂点の値もすべて自動的に決まっていくことに着目しよう！

ただその処理をするためには、有向辺 e = (u, v; w) に対して

  • 終点 x_{v} の値が定まったが、
  • 始点 x_{u} の値が分からない

という状況もあり得る。そのようなとき、

x_{u} = x_{v} - w

というように、有向辺を逆向きに辿るようなことも必要となる。そのため、グラフの入力データを受け取る際に、

  • 辺 e = (u, v; w) に対応して
  • 逆向きの辺 e' = (v, u; -w) もうちかする

というようにしよう。

このように工夫したグラフ上の DFS によって求められる。計算量は O(N + M) と評価できる。

コード

#include <bits/stdc++.h>
using namespace std;
using Edge = pair<int, long long>;
using Graph = vector<vector<Edge>>;

int main() {
    long long N, M, u, v, w;
    cin >> N >> M;
    Graph G(N);
    for (int i = 0; i < M; i++) {
        cin >> u >> v >> w, u--, v--;
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, -w);
    }

    vector<bool> seen(N, false);
    vector<long long> res(N);
    auto rec = [&](auto rec, int v) -> void {
        seen[v] = true;
        for (auto [v2, w] : G[v]) {
            if (seen[v2]) continue;
            res[v2] = res[v] + w;
            rec(rec, v2);
        }
    };
    for (int v = 0; v < N; v++) {
        if (seen[v]) continue;
        res[v] = 0;
        rec(rec, v);
    }
    for (auto val : res) cout << val << " ";
    cout << endl;
}