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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3573][Hnoi2014]米特运输  

2014-11-04 09:28:25|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3573: [Hnoi2014]米特运输


题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
const int N = (int)500000+10;
const double eps = 1e-9;
int n,m;
double data[N],base[N];
struct Point{
Point(){next = NULL;}
int d;Point *next;
void push(int a){
Point *i = new Point();
i->next = next;next = i;
i->d = a;
}
}point[N];
int scan(){int i=0;scanf("%d",&i);return i;}
queue<int>dui;
short v[N];
void bfs(){
dui.push(1);
v[1]=1;base[1]= log(1);
while(!dui.empty()){
int now=dui.front(),cot=0;dui.pop();
for(Point *i = point[now].next;i!=NULL;i=i->next)
if(!v[i->d])cot++;

for(Point *i = point[now].next;i!=NULL;i=i->next)
if(!v[i->d]){
v[i->d]=1;
base[i->d] = base[now]+log(cot);
dui.push(i->d);
}
base[now] = base[now] + log(data[now]);
}
}
int main(){
// freopen("input.txt","r",stdin);
int i,j,a,b;
n = scan();
for(i=1;i<=n;i++)data[i] = scan();
for(i=1;i<n;i++){
a = scan();b = scan();
point[a].push(b);
point[b].push(a);
}
bfs();
int ans = 0, last = 1;
sort(base+1,base+1+n);
for(i=1;i<=n;i++)
if(base[i] > 1e200)exit(1);
for(i=2;i<=n+1;i++)
if(fabs(base[i] - base[last]) > eps || i==n+1){
//printf("%d %d\n",last,i);
ans = max(ans,i-last);
last = i;
}
printf("%d\n",n-ans);
// while(1);
return 0;
}

题解:
乱搞
不难发现确定一个点的值那么整棵树的值也就唯一确定了,那么对于每个点推出此时根节点的值。
然后sort一遍看最长连续区间就行了
注意:
由于可能会让数变得很大,所以要取log
  评论这张
 
阅读(90)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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