Codeforces Round #141 The Road to Berland is Paved With Good Intentions

最近、蟻本で学習したばかりの2-SATの問題を解いてみました。

問題概要

ある国にはN個の町がある。また、M本の道路があり、それぞれの道路は２つの町を結んでいる。道路にはアスファルト舗装されている道路と、されていない道路がある。
国王が、「ある町xに繋がる道路をすべてアスファルト舗装せよ。」と命令をすると、労働者（海外からの移民で現地の言葉をうまく理解できない）たちは、アスファルト舗装されていない道をアスファルト舗装し、アスファルト舗装されている道からアスファルトを剥ぎ取る。 すべての道路をアスファルト舗装することはできるか？できるなら国王はどの町を工事対象として選べばよいかを出力せよ。

方針

以下では、町xを工事対象にすることをx、工事対象としないことを¬xと表す。
すべての道路をアスファルト舗装するためには、
(i)初期状態で道路(v, w)がアスファルト舗装済みだった場合は、

• v → w
• ¬v → ¬w
• w → v
• ¬w → ¬v

(ii)初期状態で道路(v, w)がアスファルト舗装されていなかった場合は、

• v → ¬w
• ¬v → w
• w → ¬v
• ¬w → v

が成り立たなければならない。
ということで、2-SATが使えます。

・・・・・

と普通に解いてしまいましたが、よく考えると2-SATなので、和積標準形の形じゃないとダメなのでは？何でうまくいったのだろう？と少し考えてみました。

・・・・・

そうか、a → b と ¬a∨bの真理値表は同じだから和積標準形に直せますね。

ソースコード

強連結成分分解の実装は、省略。

int n, m;

int main() {
    cin >> n >> m;

    V = 2*n;
    REP (i, m) {
        int a, b, c;
        cin >> a >> b >> c;
        --a, --b;

        if (c == 1) {
            add_edge(a, b);
            add_edge(a+n, b+n);
            add_edge(b, a);
            add_edge(b+n, a+n);
        }
        else {
            add_edge(a, b+n);
            add_edge(a+n, b);
            add_edge(b, a+n);
            add_edge(b+n, a);
        }
    }

    scc();

    REP (i, n) {
        if (cmp[i] == cmp[i+n]) {
            puts("Impossible");
            return 0;
        }
    }

    vector<int> cities;
    REP (i, n) {
        if (cmp[i] < cmp[i+n])
            cities.push_back(i+1);
    }

    cout << cities.size() << endl;
    REP (i, cities.size())
        cout << cities[i] << " ";
    cout << endl;

    return 0;
}