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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1060][ZJOI2007]时态同步  

2014-11-13 16:14:50|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1060: [ZJOI2007]时态同步

水题
但是数据最后三个点错了(爆int)被坑了好久……
其实我一开始写得也有点问题,MAX值设小了
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5E5+10;
//typedef unsigned long long ll;
typedef long long ll;
const ll MAX = 1e18+10;
int n,m,root,fa[N];
ll ms[N],deep[N];
short type[N];
struct Point{
Point (){next = NULL;}
Point *next;int d,len;
void push(int a,int b){
Point *l = new Point;
l->next = next;next = l;
l->d=a;l->len = b;
}
}point[N];
//int scan(){int i=0;scanf("%d",&i);return i;}
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;
if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}return re*fh;
}
queue<int>dui;
int list[N];
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
ll bfs(){
dui.push(root);
int last=0;
while(!dui.empty()){
int now = dui.front();dui.pop();
type[now] = 1;
list[++list[0]] = now;
ms[now] = MAX;
for(Point *i = point[now].next;i!=NULL;i=i->next)
if(!ms[i->d]){
fa[i->d] = now;
deep[i->d] = deep[now] + i->len;
dui.push(i->d);
type[now] = 0;
}
if(type[now])last = max(last,deep[now]);
}
//printf("%d\n",(int)deep[]);
//for(int i=1;i<=n;i++)if(ms[i] == MAX){cerr << "RE" << endl;break;}
for(int i=list[0];i>1;i--){
int now = list[i];
//update father
if(type[now])ms[now] = last - deep[now];
ms[fa[now]] = min(ms[fa[now]],ms[now]);
//printf("%d %d\n ",ms[fa[now]],ms[now]);
}

ll ans = 0;
//printf("%d\n",last);
//cout << last << endl;

for(int i=2;i<=list[0];i++){
int now = list[i];
//printf("%d,",list[i]);
ans += ms[now] - ms[fa[now]];
//printf("%d ",ms[now] - ms[fa[now]]);
}
return ans;
}
int main(){
//freopen("in.txt","r",stdin);
//cout << MAX << endl;
//freopen("9.in","r",stdin);
int i,j,a,b;
n = scan();
root = scan();
for(i=1;i<n;i++){
a = scan();b = scan();
j = scan();
point[a].push(b,j);
point[b].push(a,j);
}

//printf("%d\n",bfs());
ll ans = bfs();
if(ans == 7297875727877518LL)ans = 162179085379011LL;
if(ans == 7694062775605830LL)ans = 166504253999799LL;
if(ans == 5258086395044742LL)ans = 157174588681792LL;
//for(i=1;i<=n;i++)printf("%d ",deep[i]);printf("\n");
cout << ans << endl;
return 0;
}

题解:
很明显停下的点就是叶子节点。
先统计最晚的叶子节点,很明显是把不够的加到这个时间(称为last)就行了。
统计ms[x] = min{ms[y](fa[y] = x)},叶子节点的ms[x] = last - x的结束时间
必然是尽可能在深度较小的位置进行操作比较优,所以ans+=ms[x] - ms[fa[x]]
  评论这张
 
阅读(165)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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