2599: [IOI2011]Race
Time Limit: 70 Sec Memory Limit: 128 MB
Submit:
2590 Solved: 769
[Submit][Status][Discuss]
Description
给一棵树,每条边有权.求一条简单路径,权值和等于K,且边的数量最小.N <= 200000, K <= 1000000
Input
第一行 两个整数 n, k
第二..n行 每行三个整数 表示一条无向边的两端和权值 (注意点的编号从0开始)
Output
一个整数 表示最小边数量 如果不存在这样的路径 输出-1
Sample Input
4 3
0 1 1
1 2 2
1 3
4
0 1 1
1 2 2
1 3
4
Sample Output
2
HINT
$N<=200000,K<=1000000$
Source
Solution
树的点分治裸题,但是做法有点有趣
开始考虑的是:
正常的点分,然后每次用当前根开始BFS子树,以获得子树中每个节点到根的边权和和路径长度,并利用之前的结果和当前结果更新答案
不过貌似写挂了50s左右炸掉- -
发现其实不需要,只需要开一个100W的数组来记录 当前到根的距离为$i$的路径长度最短值
这样就可以不断对子树进行更新和对答案进行更新了
时间复杂度依旧是$O(nlogn)$
Code
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define maxn 200010
#define maxk 1000010
#define inf 0x3f3f3f3f
int n,K;
struct EdgeNode{int next,to,val;}edge[maxn<<];
int head[maxn],cnt=;
void add(int u,int v,int w) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v; edge[cnt].val=w;}
void insert(int u,int v,int w) {add(u,v,w); add(v,u,w);}
int size[maxn],maxx[maxn],num[maxk],siz,root,ans;
bool visit[maxn];
void Getroot(int now,int last)
{
size[now]=; maxx[now]=;
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=last && !visit[edge[i].to])
{
Getroot(edge[i].to,now);
size[now]+=size[edge[i].to];
maxx[now]=max(maxx[now],size[edge[i].to]);
}
maxx[now]=max(maxx[now],siz-size[now]);
if (maxx[now]<maxx[root]) root=now;
}
struct Node{int d,t;}st[maxn];
int s,top;
void DFS(int now,int dis,int tt,int last)
{
if (dis>K) return;
ans=min(ans,tt+num[K-dis]);
st[top++]=Node{dis,tt};
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=last && !visit[edge[i].to])
DFS(edge[i].to,dis+edge[i].val,tt+,now);
}
void Solve(int now)
{
root=; Getroot(now,); now=root;
s=,top=;
for (int i=head[now]; i; i=edge[i].next)
if (!visit[edge[i].to])
{
DFS(edge[i].to,edge[i].val,,now);
for (int j=s; j<=top-; j++)
num[st[j].d]=min(num[st[j].d],st[j].t);
s=top;
}
for (int i=; i<=top-; i++) num[st[i].d]=inf; num[]=;
visit[now]=;
for (int i=head[now]; i; i=edge[i].next)
if (!visit[edge[i].to])
siz=size[edge[i].to],Solve(edge[i].to);
}
int main()
{
n=read(); K=read();
for (int u,v,w,i=; i<=n-; i++) u=read()+,v=read()+,w=read(),insert(u,v,w);
memset(num,inf,sizeof(num)); num[]=;
ans=inf;
siz=maxx[]=n; Solve();
if (ans!=inf) {printf("%d\n",ans); return ;}
puts("-1");
return ;
}
AC第一道IOI ovo!