【poj1655】Balancing Act
2018-06-17 21:54:17来源:未知 阅读 ()
Description
For example, consider the tree:
Deleting node 4 yields two trees whose member nodes are {5} and {1,2,3,6,7}. The larger of these two trees has five nodes, thus the balance of node 4 is five. Deleting node 1 yields a forest of three trees of equal size: {2,6}, {3,7}, and {4,5}. Each of these trees has two nodes, so the balance of node 1 is two.For each input tree, calculate the node that has the minimum balance. If multiple nodes have equal balance, output the one with the lowest number.
Input
Output
Sample Input
1 7 2 6 1 2 1 4 4 5 3 7 3 1
Sample Output
1 2
题意
求树的重心,即选择一个结点删去,使得分出的 若干棵树的结点数 的最大值最小
题解
用size[x]表示x子树的结点数
size[x]=Σsize[yi];
mx[x]表示删去x之后的最大子树结点数
mx[x]=max{size[yi],n-size[x]};
取mx最小的结点,若有多个,取编号最小的
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<vector> 6 #define maxn 20005 7 #define inf 0x7fffffff 8 using namespace std; 9 long long read(){ 10 int x=0,f=1; char ch=getchar(); 11 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1;ch=getchar();} 12 while(ch>='0'&&ch<='9'){ x=x*10+ch-'0';ch=getchar();} 13 return x*f; 14 } 15 int T,n,ans; 16 int size[maxn],mx[maxn]; 17 vector<int> e[maxn]; 18 void dp(int x,int fa){ 19 size[x]=1; 20 for(int i=0;i<e[x].size();i++){ 21 int y=e[x][i]; 22 if(y==fa) continue; 23 dp(y,x); 24 size[x]+=size[y]; 25 mx[x]=max(mx[x],size[y]); 26 } 27 mx[x]=max(mx[x],n-size[x]); 28 if(mx[x]<mx[ans]) ans=x; 29 if(mx[x]==mx[ans]&&x<ans) ans=x; 30 } 31 int main(){ 32 T=read(); 33 while(T--){ 34 n=read();ans=0; 35 mx[0]=inf; 36 for(int i=1;i<n;i++){ 37 int u=read(),v=read(); 38 e[u].push_back(v); 39 e[v].push_back(u); 40 } 41 dp(1,0); 42 printf("%d %d\n",ans,mx[ans]); 43 for(int i=1;i<=n;i++) e[i].clear(); 44 memset(size,0,sizeof(size)); 45 memset(mx,0,sizeof(mx)); 46 } 47 return 0; 48 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Longest Substring Without Repeating Characters 2019-08-16
- Win10 + vs2017 编译并配置tesseract4.1.0 2019-04-20
- L - Non-Prime Factors (质数筛选+因子分解) 2019-04-20
- A.Activity planning 2018-12-04
- PAT (Basic Level) Practice 1008 数组元素循环右移问题 2018-12-04
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash