[AtCoder] ABC 087 D – People on a Line

2019年11月24日

問題

方針

座標間の距離が与えられるので、相対的な位置が分かります。したがって、ある座標の値を \( x_i = 0 \) として、\( M \) 個の情報に誤りがあるかどうかを調べます。

グラフ

各座標をグラフの頂点として、\( M \) 個の辺からなるグラフを考えます。\( M \) 個の情報から隣接リストを作成します。この隣接リストに座標間の距離の情報も追加しておきます。この座標間の距離は辺の重みではないことに注意します。例えば、\( (L_i, R_i, D_i) \) という情報から、頂点 \( L_i \) の隣接する頂点は \( R_i \) であり、距離は \( D_i \) であり、頂点 \( R_i \) の隣接する頂点は \( L_i \) であり、距離は \( -D_i \) であるという隣接リストが得られます。

幅優先探索

よくあるグラフの幅優先探索を行います。一度も訪れたことがない頂点 \( i \) の座標を \( x_i = 0 \) として、座標 \( i \) を含むグラフを走査します。このグラフを走査するなかで、座標の値を更新してき、誤りがあるかどうかを調べます。例えば、グラフ \( G \) の頂点が \( (1, 2, 3) \) であり、点 \( 1 \) に隣接する頂点が \( 2, 3)\) であり、頂点 \( 2 \) に隣接する頂点が \( 3 \) であるとします。ここで、 頂点 \( 1 \) から幅優先探索を行うと、\( x_2, x_3 \) の値が定まります。次に、頂点 \( 2 \) から頂点 \( 3 \) へ訪れたとき、\( x_3 \) の値が更新されるとき誤りがあることになります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
struct Node {
    int id, cost;
    Node(int id, int cost) : id(id), cost(cost){}
};
 
int main() {
    int N, M;
    cin >> N >> M;
    int L[M], R[M], D[M];
    vector<Node> adj[N];
    for (int i = 0; i < M; i++) {
        cin >> L[i] >> R[i] >> D[i];
        L[i]--;
        R[i]--;
        adj[L[i]].push_back(Node(R[i], D[i]));
        adj[R[i]].push_back(Node(L[i], -D[i]));
    }
    int x[N];
    int flag[N]{};
    fill(x, x + N, INT32_MAX);
    for (int i = 0; i < N; i++) {
        if (flag[i] != 0) continue;
        x[i] = 0;
        deque<int> q;
        q.push_back(i);
        while (!q.empty()) {
            int v = q.front();
            flag[v] = 1;
            q.pop_front();
            for (int j = 0; j < adj[v].size(); j++) {
                int id = adj[v][j].id;
                int cost = adj[v][j].cost;
                if (x[id] == INT32_MAX) {
                    x[id] = x[v] + cost;
                    q.push_back(id);
                    flag[id] = 1;
                } else {
                    if (x[id] != x[v] + cost) {
                        cout << "No\n";
                        return 0;
                    }
                }
            }
        }
    }
    cout << "Yes\n";
    return 0;
}