POJ 1655 Balancing Act(树的重心)
2018-06-17 22:12:50来源:未知 阅读 ()
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 14062 | Accepted: 5937 |
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
Source
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #define lli long long int 6 using namespace std; 7 const int MAXN=2000001; 8 const int maxn=0x7fffff; 9 void read(int &n) 10 { 11 char c='+';int x=0;bool flag=0; 12 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;} 13 while(c>='0'&&c<='9') 14 x=(x<<1)+(x<<3)+c-48,c=getchar(); 15 flag==1?n=-x:n=x; 16 } 17 struct node 18 { 19 int u,v,w,nxt; 20 }edge[MAXN]; 21 int head[MAXN]; 22 int num=1; 23 int size[MAXN]; 24 int ans=maxn; 25 int out=maxn; 26 int n; 27 int mx[MAXN]; 28 void add_edge(int x,int y) 29 { 30 edge[num].u=x; 31 edge[num].v=y; 32 edge[num].nxt=head[x]; 33 head[x]=num++; 34 } 35 void dfs(int pos,int fa) 36 { 37 // cout<<pos<<endl; 38 size[pos]=1; 39 int now=0; 40 for(int i=head[pos];i!=-1;i=edge[i].nxt) 41 { 42 43 if(edge[i].v!=fa) 44 { 45 dfs(edge[i].v,pos); 46 size[pos]+=size[edge[i].v]; 47 mx[pos]=max(mx[pos],size[edge[i].v]); 48 } 49 } 50 mx[pos]=max(mx[pos],n-size[pos]); 51 if(mx[pos]<mx[ans]) 52 ans=pos; 53 if(mx[pos]==mx[ans]&&pos<ans) 54 ans=pos; 55 } 56 int main() 57 { 58 int T; 59 read(T); 60 while(T--) 61 { 62 read(n); 63 //cout<<maxn<<endl; 64 num=1; 65 memset(head,-1,sizeof(head)); 66 memset(size,0,sizeof(size)); 67 memset(mx,0,sizeof(mx)); 68 mx[0]=maxn; 69 ans=0; 70 for(int i=1;i<=n-1;i++) 71 { 72 int x,y,z; 73 read(x);read(y); 74 add_edge(x,y); 75 add_edge(y,x); 76 } 77 dfs(1,0); 78 printf("%d %d\n",ans,mx[ans]); 79 80 } 81 return 0; 82 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:T7315 yyy矩阵折叠(长)
下一篇:自制贪吃蛇——碰撞检测,增加节点
- POJ-3278 2020-04-01
- Asteroids!_poj2225 2020-02-09
- poj-1753题题解思路 2020-01-26
- POJ1852 2019-11-11
- POJ2431 优先队列+贪心 - biaobiao88 2019-11-03
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