はまやんはまやんはまやん

hamayanhamayan's blog

道路網改修 [パソコン甲子園2017 予選 J]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0366?year=2017

前提知識

考察過程

1. 全体を強連結にせよという問題に言い換えられる
2. 強連結成分については内部で辺を貼る必要は無いので、強連結成分分解をしてDAGにした状態で考えればよさそう
3. 自明そうな所から攻めてみる
4. 「入次数が0の頂点は辺が入ってこないとだめ」「出次数が0の頂点は辺が出てかないとだめ」
5. これが全部満たされれば良さそう?
6. 今回は特に構築せよという問題ではないため、その条件を満たせば、あとは最適に繋げば全体が強連結になりそう
7. 特に何も考えずに投げると通る

解法

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0366/review/3136586/hamayanhamayan/C++14

自分は強連結成分→縮約→トポソの流れをライブラリ化してあるやつがあるので、それを貼る。
(ここではトポソは使わないけど)
縮約してできたDAGについて、「入次数が0の頂点」の数をsource、「出次数が0の頂点」の数をsinkとして数える。
すると必要な辺の数はmax(soruce, sink)となるので、それが答え。
コーナーケースとして、既に全体が強連結な場合は0が答え。

int N, M;
SCCtoDAG scctodag;
int inedge[101010], outedge[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    scctodag.init(N);
    rep(i, 0, M) {
        int s, t; cin >> s >> t;
        scctodag.add_edge(s, t);
    }
    scctodag.build();

    if (scctodag.M == 1) {
        printf("0\n");
        return;
    }

    int source = 0, sink = 0;
    rep(cu, 0, scctodag.M) {
        fore(to, scctodag.newE[cu]) {
            outedge[cu]++;
            inedge[to]++;
        }
    }
    rep(cu, 0, scctodag.M) {
        if (outedge[cu] == 0) sink++;
        if (inedge[cu] == 0) source++;
    }

    int ans = max(source, sink);
    cout << ans << endl;
}