题目链接 : 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 这三个子图
1 #include2 #include 3 #include 4 #include 5 6 using namespace std; 7 8 const int MAXN = 1e5+10; 9 10 vector edge[MAXN];11 int depth[MAXN];12 bool vis[MAXN];13 int maxx, maxx1, mark1;14 int length[MAXN];15 16 int Max(int a, int b)17 {18 return a > b ? a : b;19 }20 21 void Dfs(int u, int fa)22 {23 vis[u] = 1;24 depth[u] = depth[fa] + 1;25 if(depth[u] > maxx1) {26 mark1 = u;27 maxx1 = depth[u];28 }29 int len = edge[u].size();30 for(int i = 0; i < len; i++) {31 int v = edge[u][i];32 if(v == fa) continue;33 Dfs(v, u);34 }35 }36 37 bool cmp(int a, int b)38 {39 return a > b;40 }41 42 void Init(int n)43 {44 for(int i = 0; i <= n; i++) {45 edge[i].clear();46 vis[i] = 0;47 }48 maxx = 0;49 }50 51 int main()52 {53 int n, l;54 int u, v;55 56 while(scanf("%d %d", &n, &l) != EOF) {57 Init(n);58 for(int i = 0; i < l; i++) {59 scanf("%d %d", &u, &v);60 edge[u].push_back(v);61 edge[v].push_back(u);62 }63 int cnt = 0;64 for(int i = 0; i < n; i++) {65 maxx1 = 0;66 if(vis[i] == 0) {67 depth[i] = -1;68 Dfs(i, i);69 depth[mark1] = -1;70 if(maxx1 != 0) {71 Dfs(mark1, mark1);72 }73 length[i] = (maxx1 + 1) / 2;74 if(maxx1 > maxx) maxx = maxx1;75 cnt++;76 }77 }78 sort(length, length+n, cmp);79 if(n == 1) printf("0\n");80 else if(n == 2) printf("1\n");81 else if(n == 3) printf("2\n");82 else if(cnt == 1) printf("%d\n", maxx);83 else if(length[0] == length[1] && length[1] == length[2]) {84 printf("%d\n", Max(maxx, length[0] + length[1] + 2));85 }86 else {87 printf("%d\n", Max(maxx, length[0] + length[1] + 1));88 }89 }90 91 return 0;92 }