トップ > AtCoder > AtCoder Regular Contest 093 E - Bichrome Spanning Tree

AtCoder Regular Contest 093 E - Bichrome Spanning Tree

AtCoder

「3月中に毎日1問解いて黄色になろう！」キャンペーン11問目。コンテスト中に解けなかった問題です。

問題概要

N頂点M辺のグラフが与えられるので、辺を白黒2色に塗り分ける。この時、2色両方を含む全域木が存在し、そのような全域木の重みの最小値がXになる塗り方は何通りあるか求めよ。
N≦1000、M≦2000、X≦1012

E - Bichrome Spanning Tree

解説

自明な内容から考察を進めていきます。

取り敢えず色とか関係なしに考えてみましょう。最小全域木の重み>Xの時はどう頑張っても重みをXにすることは出来ないので0を出力して終了。最小全域木の重み=Xの時は、最小全域木の構成に関係のある辺がm辺あるなら、このm辺全てが同じ色でさえなければOKです。最小全域木は複数候補が考えられますが、どれか色が違えば、それを使って最小全域木が恒星可能です。なので、答えが2M-m×(2m-2)となります。

最小全域木の重み<Xの時がやや面倒で、この時、最小値が更新されてしまうので、最小全域木を構成する辺は全て同じ色に塗らないといけません。イメージとしては、基本全ての辺を（便宜的に）黒に塗っておいて、1辺だけを白く塗ります。そうすると、全域木の重みの最小値＝「その辺を使った」という制約付きの最小全域木となるので、これとXを比較します。

  • X未満なら最小全域木を構成する辺と同じ色に塗る必要があります。最小値を更新されてしまうので。

  • Xと等しい辺の個数をmとすると、このm辺全てが最小全域木の辺と同じ色でさえなければ、X未満に全域木の重みが更新されることは一つ上で述べた通り無いのでOKです。

  • Xより大きい（この辺の数をm'とします）なら、これは自由に塗っても答えに影響を与えません。

以上の内容をまとめると、最小全域木を構成する辺の塗り方が2通りあるので、2×(2m-1)×2m'が答えです。

実装の際は、以下の流れで行います。

  1. グラフ全体で最小全域木を構成してみて、これがXより大きいなら0を出力して終了。

  2. 各辺について、「その辺を使用する」という条件付きの最小全域木の重みを記録する。

  3. 1で求めた最小全域木の重みがXと等しいなら、2で求めたデータの内重みがX（1で求めた最小全域木の重み）と等しい辺の個数を調べて、答えを計算する。

  4. 1で求めた最小全域木の重みがXより小さいなら、2のデータから「Xより小さい個数」「Xと一致する個数」「Xより大きい個数」を求めて答えを計算する。


全体での最小全域木からその辺を用いた最小全域木も頑張れば構成できる気がしますが、「頂点S、Tをつなげる時に、S-T上のパスにある一番大きな辺を削除」するので、正直計算が面倒です。蟻本のLCAにそれっぽいのありましたっけ？（無くてもダブリングで辺の最大値を記録するだけなので…）

https://beta.atcoder.jp/contests/arc093/submissions/2265662

int n, m;
vector<pair<int, ll>> edge[1010];
vector<tuple<ll, int, int>> e;

int parent[1010];
int findparent(int i) {
    return parent[i] = (i == parent[i] ? i : findparent(parent[i]));
}
void merge(int i, int j) {
    int pi = findparent(i);
    int pj = findparent(j);
    parent[pi] = pj;
    pi = findparent(i);
}

ll getMST(int l) {
    rep(i, n)   parent[i] = i;
    ll ret = 0;
    if (l != -1) {
        ret += get<0>(e[l]);
        merge(get<1>(e[l]), get<2>(e[l]));
    }
    rep(i, m) {
        ll w; int u, v;    tie(w, u, v) = e[i];
        if (findparent(u) != findparent(v)) {
            ret += w;
            merge(u, v);
        }
    }
    return ret;
}

ll modpow(ll a, ll b) {
    ll ret = 1;
    while (b) {
        if (b & 1)   ret = (ret*a) % mod;
        a = (a*a) % mod;
        b >>= 1;
    }
    return ret;
}

int main() {
    cin >> n >> m;
    ll x;   cin >> x;
    rep(i, m) {
        int u, v;  ll w;   cin >> u >> v >> w;
        u--;    v--;
        edge[u].push_back(mp(v,w));
        edge[v].push_back(mp(u,w));
        e.push_back(mt(w, u, v));
    }
    sort(all(e));
    ll mst = getMST(-1);
    if (mst > x) {
        cout << 0 << endl;
        return 0;
    }
    vector<ll> weight(m);
    rep(i, m)   weight[i] = getMST(i);
    if (mst == x) {
        int cnt = 0;
        rep(i, m)   cnt += (weight[i] == x ? 1 : 0);
        ll ret = (modpow(2, cnt) - 2 + mod) % mod;
        cout << (modpow(2, m - cnt) * ret) % mod << endl;
    }
    else {
        int same = 0, onediff = 0, candiff = 0;
        rep(i, m) {
            if (weight[i] < x) same++;
            else if (weight[i] == x)    onediff++;
            else  candiff++;
        }
        ll ret = (2 * (modpow(2, onediff) - 1 + mod)) % mod;
        cout << (modpow(2, candiff)*ret) % mod << endl;
    }
    return 0;
}

感想

コンテスト中は普通に解けませんでしたが、900点問題中々解いていなかったので、久々の実装ゲーという感じでした。レートは落ちて1900を割ったので中級者すら名乗れませんが…

F問題もbitDP+包除原理らしいので、頑張れば解けるのではないでしょうか。でぐわープロがもっと点数低いとハラスメントを投げていました。