AOJ 1332 Company Organization

これは AOJ-ICPC Advent Calendar 2015 の 19 日目の記事です。

AOJ 1332 Company Organization の解説記事です。

デバッグが大変。 文章も数式も書けないので読みにくいと思います。

問題概要

n個の集合とm個の制約が与えられる。 入力で与えられた順に制約を追加していくとき、矛盾せずに制約を最大いくつ追加できるか。

制約の種類は5種類

  1. Xi ⊆ Xj
  2. Xi = Xj
  3. Xi ≠ Xj
  4. Xi ∩ Xj = Φ
  5. Xi ∩ Xj ≠ Φ

解法

1ケース当たり O((n3 + m) log m)で解きました(AOJでは通ったけど、本番ではどうなんだろう)。

二分探索で答えを求める。 制約を満たせるかどうかの判定は以下の手順で行う。

まず、各集合を頂点とし、以下のような有向辺を持つグラフを作る。

  • Xi ⊆ Xj の制約がある場合は j -> i の辺を追加
  • Xi = Xj の場合は j <-> i の辺を追加

このグラフについて以下のあれが成り立つ。

  • 同じ閉路にある集合は全て等しい
  • Xi ∩ Xj = Φ => Xi ∩ Xjの子 = Φ
  • Xi ∩ Xj ≠ Φ => Xi ∩ Xjの親 ≠ Φ

これをもとに集合のペア Xi, Xj に以下の関係が成り立つかどうか求めて、矛盾の有無を確認する。

  • Xi = Xj
  • Xi ≠ Xj
  • Xi ∩ Xj = Φ
  • Xi ∩ Xj ≠ Φ

ソースコード

import java.io.*;
import java.math.*;
import java.util.*;

import static java.util.Arrays.*;

public class Main {
    private static final int mod = (int)1e9+7;

    final Random random = new Random(0);
    final IOFast io = new IOFast();

    /// MAIN CODE
    public void run() throws IOException {
//     int TEST_CASE = Integer.parseInt(new String(io.nextLine()).trim());
        int TEST_CASE = 1<<29;
        while(TEST_CASE-- != 0) {
            n = io.nextInt();
            m = io.nextInt();
            if(n == 0) break;
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < 3; j++) {
                    query[i][j] = io.nextInt();
                    query[i][j]--;
                }
            }
            int low = 0, high = m + 1;
            while(high - low > 1) {
                int mid = (low + high) / 2;
                if(can(mid)) low = mid;
                else high = mid;
            }
            io.out.println(low);
        }
    }
    
    int n, m;
    int[][] query = new int[10000][3];
    
    boolean can(int use) {
        StronglyConnectedComponent scc = new StronglyConnectedComponent(n);
        for(int i = 0; i < use; i++) {
            if(query[i][0] == 0) {
                scc.addEdge(query[i][2], query[i][1]);
            }
            if(query[i][0] == 1) {
                scc.addEdge(query[i][2], query[i][1]);
                scc.addEdge(query[i][1], query[i][2]);
            }
        }
        final int K = scc.scc();
        boolean[][] neq = new boolean[K][K];
        boolean[][] emp = new boolean[K][K];
        boolean[][] nemp = new boolean[K][K];
        for(int i = 0; i < use; i++) {
            final int a = scc.cmp[query[i][1]];
            final int b = scc.cmp[query[i][2]];
            if(query[i][0] == 2) {
                neq[b][a] = true;
                neq[a][b] = true;
            }
            if(query[i][0] == 3) {
                emp[b][a] = true;
                emp[a][b] = true;
            }
            if(query[i][0] == 4) {
                nemp[b][a] = true;
                nemp[a][b] = true;
            }
        }
        int[] p = new int[K];
        int[] in = new int[K];
        Arrays.fill(p, -1);
        List<List<Integer>> g = new ArrayList<List<Integer>>();
        List<List<Integer>> rg = new ArrayList<List<Integer>>();
        for(int i = 0; i < K; i++) {
            g.add(new ArrayList<Integer>());
            rg.add(new ArrayList<Integer>());
        }
        for(int i = 0; i < n; i++) {
            for(int t : scc.G.get(i)) {
                int a = scc.cmp[i];
                int b = scc.cmp[t];
                if(a != b) {
                    g.get(a).add(b);
                    rg.get(b).add(a);
                    in[b]++;
                }
            }
        }
        final int[] depth = new int[K];
        Arrays.fill(depth, -1);
        Queue<Integer> que = new ArrayDeque<Integer>();
        for(int i = 0; i < K; i++) {
            if(in[i] == 0) {
                que.add(i);
                depth[i] = 0;
            }
        }
        while(!que.isEmpty()) {
            int v = que.poll();
            for(int t : g.get(v)) if(depth[t] == -1) {
                depth[t] = depth[v] + 1;
                que.add(t);
            }
        }
        Integer[] ascend = new Integer[K];
        Integer[] descend = new Integer[K];
        for(int i = 0; i < K; i++) {
            ascend[i] = i;
            descend[i] = i;
        }
        Arrays.sort(ascend, (a,b)->depth[a]-depth[b]);
        Arrays.sort(descend, (a,b)->depth[b]-depth[a]);
        for(int i = 0; i < K; i++) {
            for(int j = 0; j < K; j++) {
                {
                    final int a = ascend[i];
                    final int b = ascend[j];
                    if(emp[a][b]) {
                        for(int t : g.get(b)) { emp[a][t] = emp[t][a] = true; }
                        for(int t : g.get(a)) { emp[b][t] = emp[t][b] = true; }
                    }
                }
                {
                    final int a = descend[i];
                    final int b = descend[j];
                    if(nemp[a][b]) {
                        for(int t : rg.get(b)) { nemp[a][t] = nemp[t][a] = true; }
                        for(int t : rg.get(a)) { nemp[b][t] = nemp[t][b] = true; }
                    }
                }
            }
        }
        for(int i = 0; i < K; i++) {
            for(int j = 0; j < K; j++) {
                if(neq[i][j] && i == j) { return false; }
                if(neq[i][j] && emp[i][i] && emp[j][j]) { return false; }
                if(emp[i][j] && nemp[i][j]) { return false; }
                if(nemp[i][j] && (emp[i][i] || emp[j][j])) { return false; }
            }
        }
        return true;
    }
    
    static
    public class StronglyConnectedComponent {
        int V;
        List<List<Integer>> G;
        List<List<Integer>> rG;
        List<Integer> vs;
        boolean[] used;
        public int[] cmp;

        public StronglyConnectedComponent(int n) {
            V = n;
            G = new ArrayList<List<Integer>>(n);
            rG = new ArrayList<List<Integer>>(n);
            vs = new ArrayList<Integer>();
            used = new boolean[n];
            cmp = new int[n];
            for (int i = 0; i < n; i++) {
                G.add(new ArrayList<Integer>());
                rG.add(new ArrayList<Integer>());
            }
        }

        public void addEdge(int from, int to) {
            G.get(from).add(to);
            rG.get(to).add(from);
        }

        private void dfs(int v) {
            used[v] = true;
            for (int i = 0; i < G.get(v).size(); i++)
                if (!used[G.get(v).get(i)])
                    dfs(G.get(v).get(i));
            vs.add(v);
        }

        private void rdfs(int v, int k) {
            used[v] = true;
            cmp[v] = k;
            for (int i = 0; i < rG.get(v).size(); i++)
                if (!used[rG.get(v).get(i)])
                    rdfs(rG.get(v).get(i), k);
        }
        
        public int scc() {
            for (int i = 0; i < V; i++)
                used[i] = false;
            vs.clear();
            for (int i = 0; i < V; i++)
                if (!used[i])
                    dfs(i);
            for (int i = 0; i < V; i++)
                used[i] = false;
            int k = 0;
            for (int i = vs.size() - 1; i >= 0; i--)
                if (!used[vs.get(i)])
                    rdfs(vs.get(i), k++);
            return k;
        }
    }

    
    /// TEMPLATEは省略
}