mayoko’s diary

プロコンとかいろいろ。

東京大学プログラミングコンテスト2013 C - 直径

解法

2 つのグラフの直径, 半径を求めて,

  • 最大値については, (直径1) + (直径2) + 1
  • 最小値については, max((半径1) + (半径2) + 1, max((直径1), (直径2)))

を求めれば良いです。

直径, 半径は O(nm) で求められるので計算量的にも間に合います。

const int INF = 1e9;

vector<int> calc(const vector<vi>& G) {
    int n = G.size();
    vector<int> ret(n);
    for (int s = 0; s < n; s++) {
        queue<int> que;
        vector<int> d(n, INF);
        d[s] = 0;
        que.push(s);
        while (!que.empty()) {
            int now = que.front(); que.pop();
            for (int next : G[now]) {
                if (d[next] > d[now]+1) {
                    d[next] = d[now]+1;
                    que.push(next);
                }
            }
        }
        for (int i = 0; i < n; i++) ret[s] = max(ret[s], d[i]);
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n1, m1, n2, m2;
    cin >> n1 >> m1;
    vector<vi> G1(n1);
    for (int i = 0; i < m1; i++) {
        int a, b;
        cin >> a >> b;
        G1[a].push_back(b);
        G1[b].push_back(a);
    }
    cin >> n2 >> m2;
    vector<vi> G2(n2);
    for (int i = 0; i < m2; i++) {
        int a, b;
        cin >> a >> b;
        G2[a].push_back(b);
        G2[b].push_back(a);
    }
    auto d1 = calc(G1);
    auto d2 = calc(G2);
    int mini = INF, maxi = 0, dia = 0;
    for (int i = 0; i < n1; i++) for (int j = 0; j < n2; j++) {
        dia = max(dia, d1[i]);
        dia = max(dia, d2[j]);
        int tmp = d1[i]+1+d2[j];
        mini = min(mini, tmp);
        maxi = max(maxi, tmp);
    }
    mini = max(mini, dia);
    cout << mini << " " << maxi << endl;
    return 0;
}