洛谷 P4408 [NOI2003]逃学的小孩 题解【树的直径】【贪心】
点击量：349
好不容易考试 1A一道NOI蓝题，不过题目相对比较简单。
题目描述
Chris家的电话铃响起了，里面传出了Chris的老师焦急的声音：“喂，是Chris的家长吗？你们的孩子又没来上课，不想参加考试了吗？”一听说要考试，Chris的父母就心急如焚，他们决定在尽量短的时间内找到Chris。他们告诉Chris的老师：“根据以往的经验，Chris现在必然躲在朋友Shermie或Yashiro家里偷玩《拳皇》游戏。现在，我们就从家出发去找Chris，一但找到，我们立刻给您打电话。”说完砰的一声把电话挂了。
Chris居住的城市由N个居住点和若干条连接居住点的双向街道组成，经过街道x需花费Tx分钟。可以保证，任两个居住点间有且仅有一条通路。Chris家在点C，Shermie和Yashiro分别住在点A和点B。Chris的老师和Chris的父母都有城市地图，但Chris的父母知道点A、B、C的具体位置而Chris的老师不知。
为了尽快找到Chris，Chris的父母会遵守以下两条规则：
- 如果A距离C比B距离C近，那么Chris的父母先去Shermie家寻找Chris，如果找不到，Chris的父母再去Yashiro家；反之亦然。
- Chris的父母总沿着两点间唯一的通路行走。
显然，Chris的老师知道Chris的父母在寻找Chris的过程中会遵守以上两条规则，但由于他并不知道A，B，C的具体位置，所以现在他希望你告诉他，最坏情况下Chris的父母要耗费多长时间才能找到Chris？
输入输出格式
输入格式：
输入文件第一行是两个整数N（3 ≤ N ≤ 200000）和M，分别表示居住点总数和街道总数。
以下M行，每行给出一条街道的信息。第i+1行包含整数Ui、Vi、Ti（1≤Ui, Vi ≤ N，1 ≤ Ti ≤ 1000000000），表示街道i连接居住点Ui和Vi，并且经过街道i需花费Ti分钟。街道信息不会重复给出。
输出格式：
输出文件仅包含整数T，即最坏情况下Chris的父母需要花费T分钟才能找到Chris。
输入输出样例
输入样例#1：4 31 2 12 3 13 4 1输出样例#1：4
Code：
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::max;
using std::min;
const int N=200800;
struct node
{
int n;
long long v;
node *nxt;
node(int n,long long v)
{
this->n=n;
this->v=v;
nxt=NULL;
}
node(){nxt=NULL;}
};
node head[N],*tail[N];
long long far=0,maxx=0;
int D[3],t;//D是直径的端点
bool used[N];
void dfs(int x)
{
if(far>maxx)
{
maxx=far;
D[t]=x;
}
node *p=&head[x];
while(p->nxt!=NULL)
{
p=p->nxt;
if(used[p->n])
continue;
far+=p->v;
used[p->n]=true;
dfs(p->n);
used[p->n]=false;
far-=p->v;
}
}
long long d[N],s[N];
int cnt=0,flag;
//d是存直径上的点，s[i]存d[i]到d[i+1]的边长
void Dfs(int x)
{
if(x==D[2])
{
d[++cnt]=x;
flag=1;
return;
}
node *p=&head[x];
while(p->nxt!=NULL)
{
p=p->nxt;
if(used[p->n])
continue;
used[p->n]=true;
Dfs(p->n);
used[p->n]=false;
if(flag==1)
{
s[cnt]=p->v;
d[++cnt]=x;
break;
}
}
}
long long l[N],sum=0;//这是到直径的距离。
void DFs(int x,long long add)//add是直径的点到最近端点的距离
{
l[x]=sum+add;
node *p=&head[x];
while(p->nxt!=NULL)
{
p=p->nxt;
if(used[p->n])
continue;
used[p->n]=true;
sum+=p->v;
DFs(p->n,add);
sum-=p->v;
used[p->n]=false;
}
}
long long b[N];
int main()
{
memset(b,0,sizeof(b));
memset(used,0,sizeof(used));
int n,m,u,v;
long long w;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
tail[i]=&head[i];
for(int i=1;i<=m;i++)
{
scanf("%d%d%lld",&u,&v,&w);
tail[u]->nxt=new node(v,w);
tail[u]=tail[u]->nxt;
tail[v]->nxt=new node(u,w);
tail[v]=tail[v]->nxt;
}
t=1;
used[1]=true;
dfs(1);//O(N)
t=2;
maxx--;
memset(used,0,sizeof(used));
used[D[1]]=true;
dfs(D[1]);//O(N)
memset(used,0,sizeof(used));
flag=0;
used[D[1]]=true;
Dfs(D[1]);//找d2，回溯直径上的点
//做前缀和b[i]指i到D[2]的距离（D[2]是d[1]）
for(int i=2;i<=cnt;i++)//直径的长度直接用b[cnt]表示
b[i]=b[i-1]+s[i-1];
//让直径上每一个点去找这一点的偏心距
memset(used,0,sizeof(used));
for(int i=1;i<=cnt;i++)
used[d[i]]=1;
for(int i=1;i<=cnt;i++)
{
sum=0;//不用处理直径上的点，可以直接带进去处理
DFs(d[i],min(b[i],b[cnt]-b[i]));
}
long long ans=0;
for(int i=1;i<=n;i++)
if(l[i]>ans)
ans=l[i];
/*for(int i=1;i<=n;i++)
printf("%d ",l[i]);*/
printf("%lld\n",ans+b[cnt]);
return 0;
}
… [Trackback]
[…] There you will find 64732 additional Info to that Topic: wjyyy.top/206.html […]