P4149 [IOI2011]Race
题目描述
给一棵树，每条边有权。求一条简单路径，权值和等于 KK，且边的数量最小。
输入格式
第一行包含两个整数 n, Kn,K。
接下来 n - 1n−1 行，每行包含三个整数，表示一条无向边的两端和权值。
注意点的编号从 00 开始。
输出格式
输出一个整数，表示最小边数量。
如果不存在这样的路径，输出 -1−1。
输入输出样例
输入 #1
4 3
0 1 1
1 2 2
1 3 4说明/提示
保证 n \leqslant 2 \times 10^5,n⩽2×105, K \leqslant 10^6K⩽106。
这道题目我是在cf161D的基础上进行操作的，在维护距离的时候，顺带维护一下边数就可以。
具体细节代码写了注释，心塞，初始化写挫了，调了两天。。。
学习博客推荐：
还有一个，没看，关于求重心的
代码:
1 //点分治
2 #include<bits/stdc++.h>
3 using namespace std;
4 typedef long long ll;
5 #pragma GCC optimize(2)
6 //#define FI(n) FastIO::read(n)
7 const int inf=0x3f3f3f3f;
8 const int maxn=2e5+10;
9 const int maxm=1e6+10;
10
11 int head[maxn<<1],tot;
12 int root,allnode,n,m,k;
13 bool vis[maxn];
14 int deep[maxn],dis[maxn],siz[maxn],maxv[maxn];//deep为维护边数，dis为距离
15 int minline[maxm],ret[maxn],num[maxn],tmp[maxn];//minline维护对应距离最小的边数，ret保存距离，num保存边数，tmp保存出现过的距离，初始化minline用到
16 int ans=inf;
17
18 namespace IO{//读入挂
19 char buf[1<<15],*S,*T;
20 inline char gc(){
21 if (S==T){
22 T=(S=buf)+fread(buf,1,1<<15,stdin);
23 if (S==T)return EOF;
24 }
25 return *S++;
26 }
27 inline int read(){
28 int x; bool f; char c;
29 for(f=0;(c=gc())<'0'||c>'9';f=c=='-');
30 for(x=c^'0';(c=gc())>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^'0'));
31 return f?-x:x;
32 }
33 inline long long readll(){
34 long long x;bool f;char c;
35 for(f=0;(c=gc())<'0'||c>'9';f=c=='-');
36 for(x=c^'0';(c=gc())>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^'0'));
37 return f?-x:x;
38 }
39 }
40 using IO::read;
41 using IO::readll;
42
43 struct node{
44 int to,next,val;
45 }edge[maxn<<1];
46
47 void add(int u,int v,int w)//前向星存图
48 {
49 edge[tot].to=v;
50 edge[tot].next=head[u];
51 edge[tot].val=w;
52 head[u]=tot++;
53 }
54
55 void init()//初始化
56 {
57 memset(head,-1,sizeof head);
58 memset(vis,false,sizeof vis);
59 for(int i=0;i<=k;i++){//初始化保存最小边数
60 minline[i]=inf;
61 }
62 tot=0;
63 }
64
65 void get_root(int u,int father)//求重心
66 {
67 siz[u]=1;maxv[u]=0;
68 for(int i=head[u];~i;i=edge[i].next){
69 int v=edge[i].to;
70 if(v==father||vis[v]) continue;
71 get_root(v,u);
72 siz[u]+=siz[v];
73 maxv[u]=max(maxv[u],siz[v]);
74 }
75
76 maxv[u]=max(maxv[u],allnode-siz[u]);
77 if(maxv[u]<maxv[root]) root=u;
78 }
79
80 void get_dis(int u,int father)//求距离，维护边数
81 {
82 if(dis[u]>k) return ;//超过K，剪枝
83 ans=min(ans,minline[k-dis[u]]+deep[u]);//更新答案
84 ret[++ret[0]]=dis[u];num[ret[0]]=deep[u];//保存新得到的数据，距离和边数
85
86 for(int i=head[u];~i;i=edge[i].next){
87 int v=edge[i].to;
88 if(v==father||vis[v]) continue;
89 int w=edge[i].val;
90 dis[v]=dis[u]+w;//更新距离
91 deep[v]=deep[u]+1;//更新边数
92 get_dis(v,u);
93 }
94 }
95
96 void cal(int u)
97 {
98 int cnt=0;
99 for(int i=head[u];~i;i=edge[i].next){
100 int v=edge[i].to;
101 int w=edge[i].val;
102 if(vis[v]) continue;
103 ret[0]=0;dis[v]=w;deep[v]=1;//初始化
104 get_dis(v,u);
105
106 for(int j=1;j<=ret[0];j++){
107 tmp[++cnt]=ret[j];//临时保存出现过的距离
108 minline[ret[j]]=min(minline[ret[j]],num[j]);//更新距离的最小边数
109 }
110 }
111 for(int i=1;i<=cnt;i++){
112 minline[tmp[i]]=inf;//初始化
113 }
114 }
115
116 void solve(int u)
117 {
118 minline[0]=0;
119 cal(u);
120 vis[u]=1;
121
122 for(int i=head[u];~i;i=edge[i].next){
123 int v=edge[i].to;
124 if(vis[v]) continue;
125 allnode=siz[v];
126 root=0;maxv[0]=inf;
127 get_root(v,u);
128 solve(root);
129 }
130 }
131
132 int main()
133 {
134 n=read();k=read();
135 init();
136 for(int i=1;i<n;i++){
137 int u=read(),v=read(),w=read();
138 u++,v++;
139 add(u,v,w);
140 add(v,u,w);
141 }
142 root=0;allnode=n;maxv[0]=inf;
143 get_root(1,0);
144 solve(root);
145 if(ans==inf) printf("-1\n");
146 else printf("%d\n",ans);
147 return 0;
148 }