首页 > 代码库 > 51Nod 1737 配对（树的重心）
51Nod 1737 配对（树的重心）
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1737
题意：
思路：
树的重心。
树的重心就是其所以子树的最大的子树结点数最少，删除这个点后最大连通块的结点数最小，也就说各个连通块尽量平衡。
这道题的话就是先求一个重心，然后求各个点到重心的距离之和。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<queue> 7 #include<cmath> 8 #include<map> 9 using namespace std;10 11 const int maxn=1e5+5;12 const int INF=0x3f3f3f3f;13 14 int n;15 16 vector<pair<int,int> > edge[maxn];17 18 int zx,sz;19 int son[maxn],vis[maxn];20 long long ww[maxn]; //各个点到重心的距离21 22 void init()23 {24 for(int i=1;i<=n;i++)25 edge[i].clear();26 memset(vis,0,sizeof(vis));27 memset(ww,0,sizeof(ww));28 sz=INF;29 zx=-1;30 }31 32 void dfs(int u)33 {34 vis[u]=1;35 son[u]=0;36 int temp=0;37 for(int i=0;i<edge[u].size();i++)38 {39 int v=edge[u][i].first;40 if(!vis[v])41 {42 dfs(v);43 son[u]+=son[v]+1; //找到该子树中的最大结点数44 temp=max(temp,son[v]+1);45 }46 }47 temp=max(temp,n-son[u]-1); //删去重心后子树最大结点数和非重心的子树比较48 if(temp<sz)49 {50 zx=u;51 sz=temp;52 }53 }54 55 void sum(int u)56 {57 vis[u]=1;58 for(int i=0;i<edge[u].size();i++)59 {60 int v=edge[u][i].first;61 if(!vis[v])62 {63 ww[v] =ww[u]+edge[u][i].second;64 sum(v);65 }66 }67 }68 69 int main()70 {71 //freopen("D:\\input.txt","r",stdin);72 while(~scanf("%d",&n))73 {74 init();75 int u,v,w;76 for(int i=1;i<=n-1;i++)77 {78 scanf("%d%d%d",&u,&v,&w);79 edge[u].push_back(make_pair(v,w));80 edge[v].push_back(make_pair(u,w));81 }82 83 dfs(1);84 memset(vis,0,sizeof(vis));85 sum(zx);86 long long ans=0;87 for(int i=1;i<=n;i++)88 ans+=ww[i];89 printf("%lld\n",ans);90 }91 }
51Nod 1737 配对（树的重心）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。