実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 765

問題概要

$N$ 頂点 $M$ 辺の有向グラフが与えられ、 $j$ 番目の有向辺は頂点 $u_j$ から頂点 $v_j$ に向かっており、重み $w_j$ を持つ。各頂点に整数を書き込む方法であって、次の条件を満たすものを1つ求めよ。ただし、与えられる入力について条件を満たす書き込み方が少なくとも1つ存在することが保証される。

条件 : 頂点 $i$ に書き込まれている値を $x_i \: (-10^{18} \leq x_i \leq 10^{18}$ とする。すべての辺 $j=1,2,\cdots,M$ について、 $x_{v_j} - x_{u_j} = w_j$ が成り立つ。

制約

入力はすべて整数。
$2 \leq N \leq 2 \times 10^5$
$1 \leq M \leq \min \bigg( 2 \times 10^5, \dfrac{N(N-1)}{2} \bigg)$
グラフに自己ループ・多重辺はない。
$|w_j| \leq 10^9$

考察

とりあえずサンプルケース1で考えてみる。頂点 $1$ から矢印に沿って数を書き込んでいく。このとき、最初に見る頂点には $0$ を書き込む。

したがって、同じ連結成分に属する頂点集合に関しては、1つを決めれば残りは芋づる式に決まっていくことがわかる。

ただ、このこの方針には一つ落とし穴がある。例えば次のケースを考えてみよう。

サンプルケース1のグラフに、 $4 \xrightarrow{7} 1$ の辺を新たに加えた。

サンプルケース1のグラフに、 $4 \xrightarrow{7} 1$ の辺を新たに加えた。

頂点 $4$ に書き込む数を決定したい。しかし、これまでは「矢印の始点に書き込む数が決まっていて終点が未確定」の場合を前提として進めていったが、今回はその逆だ。どうすればよいだろうか。考えられるシンプルな選択肢としては次の2つだ。

ある連結成分をトポロジカルソートし、処理後に得られる最初の頂点から書き込む数を決定していく。
終点から逆算して値を決める。

1つ目も確かに良さそうなのだが、実はトポロジカルソートが使えるのは DAG (有向非巡回グラフ) の場合に限定される。今回は制約の形からグラフ内に閉路が存在することもあり得るので、この方針は棄却される。

したがって、2つ目の方針をとってみる。どのように逆算していけばよいだろう。

答えは単純だ。逆算できるように逆向きの辺を張ればよいのである。

つまり、入力の段階で $u_j \xrightarrow{w_j} v_j$ と $v_j \xrightarrow u_j$ の2つの辺を張っておくことで、先ほどの芋づる式に値を決めていく方針を貫くことができる。

ここまでわかれば後は実装するだけ。連結成分の探索は DFS または BFS でよいだろう。コードでは DFS による例を示している。

DFS の再帰内の処理では、未訪問の頂点を見る際に、訪問先の頂点に書き込む数を決めていくような流れをとっている。

なお、重み付き Union-Find といった高等テクを使わずとも、「DFS の再帰処理内か否か」で同じ連結成分か否かを判別することができる。

コード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
template <class T>
using Graph = vector<vector<T>>;

#define all(x) (x).begin(), (x).end()
#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

struct Edge
{
    int to;
    ll cost;
};

void DFS(Graph<Edge> &G, vector<bool> &visited, vector<ll> &ans, int &now)
{
    visited[now] = true;   

    for (auto next : G[now])
    {
        if (!visited[next.to]) {
            ans[next.to] = ans[now] + next.cost;
            DFS(G, visited, ans, next.to);
        }
    }
}

int main()
{
    int N, M;
    cin >> N >> M;
    Graph<Edge> G(N);
    rep(i, 0, M)
    {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        u--, v--;
        G[u].push_back({v, w});
        G[v].push_back({u, -w});
    }

    vector<ll> ans(N, 0);
    vector<bool> visited(N, false);
    rep(i, 0, N)
    {
        if (!visited[i])
            DFS(G, visited, ans, i);
    }
    
    for (auto &&x : ans) cout << x << " ";
    cout << endl;
}