注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

cf#260 div2 E Civilization  

2015-07-22 13:50:17|  分类: Codeforces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://codeforces.com/contest/455/problem/C
题意:
n 个点,m 条边,q 次操作。
操作 1:询问 a 所在联通块的最大直径。
操作 2:如果 a 和 b 不在一个联通块,则连一条边使其联通,且使得新联通块的最大直径最小。
题解:
利用并查集维护联通块的直径。
1. 找出每个联通块的直径,直径的一端做为联通块的根,记录每个根所在联通块的直径。
2. 如果是操作 1 直接输出;如果是操作 2,合并两个联通块 fx 和 fy,按直径更大的 fx 合并。如果想要新联通块的最大直径最小,则应该是两个联通块的直径中间连一条边,所以新的长度为两个直径各取一半 +1 。当然新的长度可能小于 fx 的直径,总之取 max 即可。最后将 fy 的根修改为 fx 即可。

int n,m,q;
struct Edge{
int v,next;
}edge[N*2];
int e,head[N];
int fa[N],dis[N];
int ans,u,root;

void init(){
memset(head,-1,sizeof(head));
e=1;
for(int i=1;i<=n;i++) fa[i]=i;
memset(dis,0,sizeof(dis));
}

void add(int u,int v){
edge[e].v=v;
edge[e].next=head[u];
head[u]=e++;
}

int Find(int x){
return x==fa[x]?x:fa[x]=Find(fa[x]);
}

void dfs(int tmp,int pre,int step) {
fa[tmp]=root;
if(step > ans){
ans=step;
u=tmp;
}
for(int i=head[tmp];i!=-1;i=edge[i].next){
if(edge[i].v != pre){
dfs(edge[i].v,tmp,step+1);
}
}
}

void Merge(int x,int y){
int fx=Find(x);
int fy=Find(y);
if(fx == fy) return;
if(dis[fx] < dis[fy]) swap(fx,fy);
dis[fx]=max(dis[fx],(dis[fx]+1)/2+(dis[fy]+1)/2+1);
fa[fy]=fx;
}


int main()
{
int a,b,c;
while(scanf("%d%d%d",&n,&m,&q)!=EOF){
init();
fr(m) {
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
for(int i=1;i<=n;i++){
if(fa[i] != i) continue;
ans=-1;root=i;
dfs(i,-1,0);
ans=-1;root=u;
dfs(u,-1,0);
dis[root]=ans;
}
while(q--){
scanf("%d",&a);
if(a == 1){
scanf("%d",&a);
printf("%d\n",dis[Find(a)]);
}
else {
scanf("%d%d",&b,&c);
Merge(b,c);
}
}
}
return 0;
}

  评论这张
 
阅读(71)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017