hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

Codeforces Round #527 Div.3 E: Minimal Diameter Forest

問題概要

原文 → Problem - E - Codeforces

 N 頂点からなる森が与えられる。このグラフに対して辺を追加して木を作りたい。木の直径が最小になるように辺を追加した時の、その直径の値と追加すべき辺を列挙せよ。

解説

森を木に分割して、木同士をマージすることを考えます。木  T_1 T_2 をマージする際にどの頂点を選択するかが問題ですが、これは木  T_1 の中心  c_1 と木  T_2 の中心  c_2 の間を接続するのが最適です。木  T_1 の直径を  D_1と、中心からの距離最大値 (つまり半径) を  d_1 とします。 T_2 についても同様に  D_2, d_2 を定義します。このように接続することで、マージされた後の木の直径は  \max \left( D_1, D_2, d_1 + d_2 + 1 \right) となります。

中心同士を順に接続していくことになりますが、中心の頂点のみからなるグラフはどのような形をしていればよいでしょうか?直径を最小化するには、スターグラフにように接続することが最適です。また、元の木において直径が最大になるものをスターグラフ中の次数が多くなる頂点に割り当てることで、最適なマージが可能になります。

ソースコード

vector<int> G[1010];
int N, M, used[1010];

void dfs(int cur, vector<int> &dist) {
    for(auto to : G[cur]) {
        if(dist[to] >= 0) continue;
        dist[to] = dist[cur] + 1;
        dfs(to, dist);
    }
}

pair<int, int> get_graph_info(int id) {
    vector<int> d0(N, -1), d1(N, -1), d2(N, -1);
    d0[id] = 0; dfs(id, d0);

    // 直径は p1 と p2 をつなぐパスになる
    int p1 = max_element(d0.begin(), d0.end()) - d0.begin();
    d1[p1] = 0; dfs(p1, d1); // d1 は p1 からの距離を記憶したもの
    int p2 = max_element(d1.begin(), d1.end()) - d1.begin();
    d2[p2] = 0; dfs(p2, d2); // d2 は p2 からの距離を記憶したもの
    int diam = d2[p1];

    int mi = INF, res = -1;
    for(int i=0; i<N; i++) {
        if(d1[i] < 0 or d2[i] < 0) continue;
        used[i] = true;
        int tmp = max(d1[i], d2[i]);
        if(mi > tmp) mi = tmp, res = i;
    }
    return make_pair(diam, res);
}

signed main() {
    scanf("%lld%lld", &N, &M);
    
    for(int i=0; i<M; i++) {
        int u, v; scanf("%lld%lld", &u, &v);
        u--; v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    // (直径, 中心となる頂点)
    vector< pair<int, int> > cand;
    for(int i=0; i<N; i++) {
        if(used[i]) continue;
        pair<int, int> info = get_graph_info(i);
        cand.push_back(info);
    }

    sort(cand.rbegin(), cand.rend());
    vector< pair<int, int> > edges;
    for(int i=1; i<cand.size(); i++) {
        int u = cand[0].second, v = cand[i].second;
        edges.emplace_back(u+1, v+1);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    pair<int, int> whole = get_graph_info(0);
    printf("%lld\n", whole.first);
    for(auto e : edges) {
        printf("%lld %lld\n", e.first, e.second);
    }
    return 0;
}

本番ではスターグラフにする発想が思い浮かばず。冷静に考えれば自然な発想なので、もっと絵をかいてやるべきでした。