AOJ2732 - Modern Announce Network

問題

Modern Announce Network | Aizu Online Judge

解法

入力より生徒を頂点、コネクションを重み1の辺とするグラフを構築することができます。このようにして得られたグラフから、さらに各学年の生徒を一つの頂点にまとめたグラフを考えます。あらかじめネットワークを構築しておけば、スタートとなる頂点は任意に選べることから、解くべき問題は今まとめた3個の頂点をターミナル集合とする最小シュタイナー木問題となります。最小シュタイナー木問題はNP困難な問題であることが知られていますが、今回はターミナルが3つであることから多項式時間解法が存在します。

証明は省略しますがターミナルが3つの場合、最小シュタイナー木はパスグラフまたはY字型のグラフにしかなり得ません。よって各ターミナルについて、を始点、(からまでの距離、経路中の最小の頂点番号)を値とする最短経路を求めます。そして各頂点に対して、各ターミナルからの距離の和と、含みうる頂点番号の最小値を計算します。この中で最適なものが解となります。

ソースコード

#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

using P = pair<int, int>; // (距離，パス上の最小頂点id)
using PPI = pair<P, int>;

const int inf = 1 << 28;

int N, A, B, C;

P cost[3][20000];
vector<int> G[20000];
int old_id[20000]; // 変換後のグラフG'の頂点v'に対応する元の頂点v

void dijkstra(int s) {
    for (int v = 0; v < N; v++) {
        cost[s][v] = {inf, inf};
    }

    cost[s][s] = {0, old_id[s]};

    priority_queue<PPI, vector<PPI>, greater<PPI>> Q;
    Q.push({{0, old_id[s]}, s});
    while (!Q.empty()) {
        auto q = Q.top();
        Q.pop();
        P val = q.first;
        int v = q.second;

        if (cost[s][v] < val) {
            continue;
        }

        for (int to : G[v]) {
            P nval = make_pair(val.first + 1, min(val.second, old_id[to]));
            if (cost[s][to] > nval) {
                cost[s][to] = nval;
                Q.push({nval, to});
            }
        }
    }
}

int main() {
    static int num[3];
    cin >> N;
    for (int i = 0; i < 3; i++) {
        cin >> num[i];
    }
    static int min_id[3] = {inf, inf, inf};

    static int group[20000];
    memset(group, -1, sizeof(group));
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < num[i]; j++) {
            int x;
            cin >> x;
            x--;
            group[x] = i;
            min_id[i] = min(min_id[i], x);
        }
    }
    map<int, int> mp;
    int id = 3;

    for (int i = 0; i < 3; i++) {
        old_id[i] = min_id[i];
    }

    for (int v = 0; v < N; v++) {
        if (0 <= group[v] and group[v] < 3)
            mp[v] = group[v];
        else {
            mp[v] = id++;
            old_id[mp[v]] = v;
        }
    }

    int M;
    cin >> M;
    for (int i = 0; i < M; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;

        G[mp[x]].emplace_back(mp[y]);
        G[mp[y]].emplace_back(mp[x]);
    }

    // Dijkstra
    for (int s = 0; s < 3; s++) {
        dijkstra(s);
    }

    P ans = {inf, inf};
    for (int v = 0; v < id; v++) {
        ans = min(ans, {cost[0][v].first + cost[1][v].first + cost[2][v].first,
                        min({cost[0][v].second, cost[1][v].second,
                             cost[2][v].second})});
    }
    cout << ans.first << " " << ans.second + 1 << endl;

    return 0;
}

感想

某企画の4問目です。femtoさんとペアプロしながら通しました。三点を結ぶ最小ネットワークの構築する問題としてはARC019C - 最後の森があります。