Gym 100781A Adjoin the Networks——树的直径

Gym 100781A Adjoin the Networks——树的直径

题意：给你一个森林，让你把森林连城一棵树，使得这棵树的直径最小

思路：首先求出树的直径，为了保证最终直径最小先求出最大的直径，然后拿其他直径不断与最大的直径合并，合并规则如下：

设当前最大直径为a，需合并的直径为b

若a为奇数，那么若a=b，最大值+2，若a = b + 1，最大值+1，若a=b+2，最大值+1

若a为偶数，那么若a=b，最大值+1，若a=b+1， 最大值+1

这个自己画画就知道了

#include #include #include #include #include using namespace std;const int maxn = 1e5 + 10;int n, m;vector G[maxn];bool vis1[maxn], vis2[maxn];int start, terminal, dis, D[maxn];void dfs1(int pre, int u, int d) { vis1[u] = true; for (int i = 0 ; i < G[u].size(); i++) { int v = G[u][i]; if (v == pre || vis1[v]) continue; if (d + 1 > dis) { dis = d + 1; start = v; } dfs1(u, v, d + 1); }}void dfs2(int pre, int u, int d) { vis2[u] = true; for (int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if (v == pre || vis2[v]) continue; if (d + 1 > dis) { dis = d + 1; terminal = v; } dfs2(u, v, d + 1); }}int main() { scanf("%d %d", &n, &m); int u, v; for (int i = 0; i < m; i++) { scanf("%d %d", &u, &v); G[u].push_back(v); G[v].push_back(u); } int cnt = 0; for (int i = 0; i < n; i++) { if (vis1[i]) continue; if (G[i].size() == 0) { vis1[i] = vis2[i] = true; D[cnt++] = 0; continue; } start = dis = 0; dfs1(-1, i, 0); terminal = dis = 0; dfs2(-1, start, 0); D[cnt++] = dis; } sort(D, D+cnt, greater()); int ans = D[0]; for (int i = 1; i < cnt; i++) { if (ans & 1) { if (ans - D[i] == 0) ans += 2; else if (ans - D[i] == 1) ans += 1; else if (ans - D[i] == 2) ans += 1; } else { if (ans - D[i] == 0) ans += 1; else if (ans - D[i] == 1) ans += 1; } } printf("%d\n", ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。