首页 > 代码库 > 【DFS】Gym - 100781A - Adjoin the Networks
【DFS】Gym - 100781A - Adjoin the Networks
给你一个森林,让你把它连接成一颗树,使得直径最小。
就求出每颗树的重心以后,全都往直径最大的那个的重心上连,一般情况是最大/2+次大/2+1,次大/2+第三大/2+2 中取较大者。
还有些特殊情况要特判处理一下。
#include<cstdio> #include<algorithm> using namespace std; int v[200010],first[100010],next[200010],e; void AddEdge(int U,int V){ v[++e]=V; next[e]=first[U]; first[U]=e; } int n,m; int S1; bool vis[100010],vis2[100010]; int maxD; void dfs(int U,int d){ vis[U]=1; if(d>maxD){ maxD=d; S1=U; } for(int i=first[U];i;i=next[i]){ if(!vis[v[i]]){ dfs(v[i],d+1); } } } void df2(int U,int d){ vis2[U]=1; maxD=max(maxD,d); for(int i=first[U];i;i=next[i]){ if(!vis2[v[i]]){ df2(v[i],d+1); } } } int b[100010],be; int main(){ // freopen("a.in","r",stdin); int x,y; scanf("%d%d",&n,&m); if(n==1){ puts("0"); return 0; } if(n==2){ puts("1"); return 0; } for(int i=1;i<=m;++i){ scanf("%d%d",&x,&y); ++x; ++y; AddEdge(x,y); AddEdge(y,x); } for(int i=1;i<=n;++i){ if(!vis[i]){ maxD=0; dfs(i,0); maxD=0; df2(S1,0); b[++be]=maxD; } } sort(b+1,b+be+1); int tmp=max(2,max(b[be]/2+b[be]%2+b[be-1]/2+b[be-1]%2+(be!=1),b[be])); if(be>=3){ tmp=max(tmp,b[be-2]/2+b[be-2]%2+b[be-1]/2+b[be-1]%2+2); } printf("%d\n",tmp); return 0; }
【DFS】Gym - 100781A - Adjoin the Networks
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。