東京大学プログラミングコンテスト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; }