Codeforces 455C Civilization：树的直径 + 并查集【合并树后直径最小】

题目链接：http://codeforces.com/problemset/problem/455/C

题意：

　　给你一个森林，n个点，m条边。

　　然后有t个操作。共有两种操作：

　　　　（1）1 x：

　　　　　　输出节点x所在树的直径。

　　　　（2）2 x y：

　　　　　　如果x,y不在同一棵树上的话，用一条边连接x,y所在的树，并且使得到的新树的直径尽可能小。

题解：

　　首先对于初始状态，算出每一棵树的直径d[find(i)]。

　　每次合并树的时候，因为要尽可能让新树直径变小，所以显然这条边要分别连接两棵树直径的“中点”。

　　所以新树的直径 = max( d[x], d[y], ceil(d[x]/2)+ceil(d[y]/2)+1 )

　　然后用并查集合并就好啦。

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <math.h>

 #include <vector>

 #define MAX_N 300005

 using namespace std;

 int n,m,t;

 int maxd;

 int op,ed;

 int d[MAX_N];

 int par[MAX_N];

 vector<int> edge[MAX_N];

 void init_union_find()

 {

     for(int i=;i<=n;i++)

     {

         par[i]=i;

     }

 }

 int find(int x)

 {

     return par[x]==x ? x : par[x]=find(par[x]);

 }

 void unite(int x,int y)

 {

     int px=find(x);

     int py=find(y);

     if(px==py) return;

     par[px]=py;

 }

 bool same(int x,int y)

 {

     return find(x)==find(y);

 }

 void read()

 {

     scanf("%d%d%d",&n,&m,&t);

     init_union_find();

     int x,y;

     for(int i=;i<=m;i++)

     {

         scanf("%d%d",&x,&y);

         edge[x].push_back(y);

         edge[y].push_back(x);

         unite(x,y);

     }

 }

 void dfs(int now,int p,int nd,int &v)

 {

     if(nd>maxd)

     {

         maxd=nd;

         v=now;

     }

     for(int i=;i<edge[now].size();i++)

     {

         int temp=edge[now][i];

         if(temp!=p) dfs(temp,now,nd+,v);

     }

 }

 void work()

 {

     for(int i=;i<=n;i++)

     {

         if(find(i)==i)

         {

             maxd=-;

             dfs(i,-,,op);

             maxd=-;

             dfs(op,-,,ed);

             d[i]=maxd;

         }

     }

     int opt,x,y;

     while(t--)

     {

         scanf("%d",&opt);

         if(opt==)

         {

             scanf("%d",&x);

             printf("%d\n",d[find(x)]);

         }

         else

         {

             scanf("%d%d",&x,&y);

             if(!same(x,y))

             {

                 d[find(y)]=max(max(d[find(x)],d[find(y)]),

                     (int)(ceil(d[(find(x))]/2.0)+ceil(d[find(y)]/2.0)+));

                 unite(x,y);

             }

         }

     }

 }

 int main()

 {

     read();

     work();

 }

巴特西

Codeforces 455C Civilization：树的直径 + 并查集【合并树后直径最小】

最新文章

热门文章