ABC087 D

問題

• DFSのようなもの
• 読むのも難しかった
• 考え方も難しい
• 操作については全探索しているイメージ
• 矛盾が所持たら終了
• List配列を用いる面白い解答

解析解答

public class Main {

    static int n, m;　　// n : 人数　m: データ数
    static int[] l, r, d;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        l = new int[m];
        r = new int[m];
        d = new int[m];
        List<Edge>[] edges = new ArrayList[n];
// Listの配列を作成している
// 配列の要素数がn個で人の数に対応している
// Listの添字は人の番号
// 次の人の番号とそこにいくまでの距離を所持している
// 一つの添字に何個も要素が入る場合もある。
        for (int i = 0; i < n; i++)
            edges[i] = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            l[i] = sc.nextInt() - 1;
            r[i] = sc.nextInt() - 1;
            d[i] = sc.nextInt();
            edges[l[i]].add(new Edge(r[i], d[i]));
            edges[r[i]].add(new Edge(l[i], -d[i]));
        }

• 入力が終わる

        boolean ok = true;
// n人分のint型????
// 添字は人の投資番号
// 中身はいる場所
        int[] x = new int[n];
        Arrays.fill(x, -Integer.MAX_VALUE);  //初期値を代入
        for (int i = 0; i < n; i++) {
// 初めての処理
            if (x[i] == -Integer.MAX_VALUE) {
// 毎回のスタートは0にする。
                x[i] = 0;
                ok &= dfs(i, x, edges);
            }
        }
        System.out.println(ok ? "Yes" : "No");
    }

• メインとなるDFSメソッド

    static boolean dfs(int i, int[] x, List<Edge>[] edges) {
// i番目の人について
// 配列は参照型 => 参照呼び出しで値を変えられる。
        List<Edge> edge = edges[i];
// 行き先取得する。
// 要素0の場合もある
// 要素全部試す
        for (int j = 0; j < edge.size(); j++) {
            int to = edge.get(j).to;
            int cost = edge.get(j).cost;
// 初めてその人間に処理する場合の処理
            if (x[to] == -Integer.MAX_VALUE) {
                x[to] = x[i] + cost;
// 行った先の人に登録されている移動情報の処理をする。
// 再帰呼び出し
                if (!dfs(to, x, edges))
                    return false;
            } else {
// 初めてじゃない場合
                if (x[i] + cost != x[to])
                    return false;
            }
        }
        return true;
    }

• Edgeクラスの定義

    static class Edge {
        int to, cost;   // 移動先と距離を所持

        Edge(int to, int cost) {
            this.to = to;
            this.cost = cost;
        }
    }
}

感想

難しかった。400点問題とは思えない.DFSに慣れていないだけかもしれない.別クラスを用意するのは少し慣れてきた.自分でコードも書いてみたがほとんど同じコードになってしまった.
DFSは再帰呼び出しして終わるまで繰り返す必要がある。