题目链接 : http://codeforces.com/gym/100781/attachments
题意 :
有n个编号为0-n-1的点, 给出目前已经有的边(最多n-1条), 问如何添加最少的边, 使得整个图连通, 且其中两点间距离的最大值最小, 一条边距离为1单位
思路 :
两点间距离的情况 : 1. 子图中任意两点间距离 2.两个子图中两点间的距离
无论如何添加边对第一种的距离都没有影响, 对第二种却有影响
考虑添加一条边连通两个子图后, 最长的距离为 子图1中距离添加边的节点的最长的距离 + 子图2中距离添加边的节点的最长的距离 + 添加的1条边的距离
所以选择添加边的节点是 在某个子图中, 使所有节点到它的最长距离最小的点
但是不用算出这个点, 只需要这个距离, 这个距离就是一个子图中距离最长两点距离的一半, 即(max_length + 1) / 2
一个图中最长距离求法是在对某个子图任一节点深搜, 搜到距离最长的点, 再对这个点深搜, 记录最长距离(新技能)
最终取 : 情况1 和 情况2 距离最大值
注意情况二中, 如果存在三个子图最大(max_length + 1) / 2 都相等, 最终答案是要加2条边的距离而不是加1条, 比如0-1 1-2 3-4 这三个子图
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector> using namespace std; const int MAXN = 1e5+; vector<int> edge[MAXN];
int depth[MAXN];
bool vis[MAXN];
int maxx, maxx1, mark1;
int length[MAXN]; int Max(int a, int b)
{
return a > b ? a : b;
} void Dfs(int u, int fa)
{
vis[u] = ;
depth[u] = depth[fa] + ;
if(depth[u] > maxx1) {
mark1 = u;
maxx1 = depth[u];
}
int len = edge[u].size();
for(int i = ; i < len; i++) {
int v = edge[u][i];
if(v == fa) continue;
Dfs(v, u);
}
} bool cmp(int a, int b)
{
return a > b;
} void Init(int n)
{
for(int i = ; i <= n; i++) {
edge[i].clear();
vis[i] = ;
}
maxx = ;
} int main()
{
int n, l;
int u, v; while(scanf("%d %d", &n, &l) != EOF) {
Init(n);
for(int i = ; i < l; i++) {
scanf("%d %d", &u, &v);
edge[u].push_back(v);
edge[v].push_back(u);
}
int cnt = ;
for(int i = ; i < n; i++) {
maxx1 = ;
if(vis[i] == ) {
depth[i] = -;
Dfs(i, i);
depth[mark1] = -;
if(maxx1 != ) {
Dfs(mark1, mark1);
}
length[i] = (maxx1 + ) / ;
if(maxx1 > maxx) maxx = maxx1;
cnt++;
}
}
sort(length, length+n, cmp);
if(n == ) printf("0\n");
else if(n == ) printf("1\n");
else if(n == ) printf("2\n");
else if(cnt == ) printf("%d\n", maxx);
else if(length[] == length[] && length[] == length[]) {
printf("%d\n", Max(maxx, length[] + length[] + ));
}
else {
printf("%d\n", Max(maxx, length[] + length[] + ));
}
} return ;
}