JAG Practice Contest for ACM-ICPC Asia Regional 2015 F - Modern Announce Network

この問題好き(だけどプロの人は典型とか言いそう)。

問題

jag2015autumn.contest.atcoder.jp

解法

考えやすくするために「1年生の集合」「2年生の集合」「3年生の集合」という集合を表した頂点(これらを A, B, C とする)を考えます。すると, 求めるべきなのは 頂点 A, B, C が連結になるように最小で何本の辺をつけなければならないか, という問題になります。

で, ここで注目したいのは, 頂点 A, B, C が連結になるように最小で何本の辺をつけなければならないか, という問題と, 頂点 A, B, C からの距離の和の最小値はいくらか, という問題が等価になることです。

これは, 結局コストが最小になる場合以下の図のように白い頂点を起点に青, 赤, 緑(それぞれ 1 年生, 2 年生, 3 年生)をつなぐ感じになることからわかります(白い頂点から青い頂点に行く辺の中に, 白い頂点から赤い頂点に行く際に使う辺が全く無いなどということが大事)。

ちなみに, 白い頂点が存在しない(例えば赤い頂点を起点に青, 緑の頂点につなぐほうが得な場合)もありますが, その場合も同じ議論が成り立ちます。

ということで, 上で書いたように A, B, C からの距離の和が最小になる値を求めればひとつの答えがわかりますが, この問題でもうひとつ難しいのは, 起点にすべき頂点も求めないといけないところです。起点にすべき頂点は, 上の図で白い頂点でも赤い頂点でも良いし, また白 -> 青の頂点の中で使われる頂点でも良いので, 経路の中でラベルの一番小さいものを選ばなければなりません。

これは, ダイクストラの中で上手くやりました。コード見てもらうほうが早いですが, pair の中で, (距離, 今まで通った頂点の集合の, ラベルの最小値)というのを持っておくことで, 解決しています。

まとめ

• 頂点の集合をひとつの頂点とみなして考えると考えがスッキリするなぁと思いました

typedef pair<int, int> pii;

const int MAXN = 10010;

struct edge {
    int v;
    ll w;
    edge() {}
    edge(int v, ll w) : v(v), w(w) {};
};

vector<pii> dijkstra(int n, vector<vector<edge> >& G, int s) {
    vector<pii> d(n, pii(MAXN, MAXN)); d[s] = pii(0, s);
    priority_queue<pair<pii, int>, vector<pair<pii, int> >, greater<pair<pii, int> > > que;
    que.push(make_pair(d[s], s));
    while (!que.empty()) {
        auto p = que.top(); que.pop();
        int u = p.second;
        pii dist = p.first;
        if (dist > d[u]) continue;
        for (edge e : G[u]) {
            if (d[e.v] > pii(d[u].first+e.w, min(d[u].second, e.v))) {
                d[e.v] = pii(d[u].first+e.w, min(d[u].second, e.v));
                que.push(make_pair(d[e.v], e.v));
            }
        }
    }
    return d;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, A, B, C;
    cin >> N >> A >> B >> C;
    vector<vector<edge> > G(N+3);
    for (int i = 0; i < A; i++) {
        int a;
        cin >> a;
        a--;
        G[a].emplace_back(N, 0);
        G[N].emplace_back(a, 0);
    }
    for (int i = 0; i < B; i++) {
        int a;
        cin >> a;
        a--;
        G[a].emplace_back(N+1, 0);
        G[N+1].emplace_back(a, 0);
    }
    for (int i = 0; i < C; i++) {
        int a;
        cin >> a;
        a--;
        G[a].emplace_back(N+2, 0);
        G[N+2].emplace_back(a, 0);
    }
    int M;
    cin >> M;
    for (int i = 0; i < M; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        G[x].emplace_back(y, 1);
        G[y].emplace_back(x, 1);
    }
    vector<vector<pii> > d(3);
    for (int i = 0; i < 3; i++) d[i] = dijkstra(N+3, G, N+i);
    pii ans(MAXN, MAXN);
    for (int i = 0; i < N; i++) {
        pii tmp;
        tmp.second = MAXN;
        for (int j = 0; j < 3; j++) {
            tmp.first += d[j][i].first;
            tmp.second = min(tmp.second, d[j][i].second);
        }
        ans = min(ans, tmp);
    }
    cout << ans.first << " " << ans.second+1 << endl;
    return 0;
}