2599: [IOI2011]Race
Description
给一棵树,每条边有权.求一条路径,权值和等于K,且边的数量最小.
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
这是一道神奇的点分治。。。
蒟蒻wy默默地表示查了一下午的WA。。。
#include<queue>
#include<cstdio>
using namespace std;
int N,K,tot,Focus,T;
const int INF=0x3f3f3f3f;
int first[200010];
int next[400010];
int end[400010];
int value[400010];
int mark[200010];
int Dist[200010];
int dep[200010];
int size[200010];
int maxx[200010];
int P[1000010];
int f[1000010];
queue <int> Q;
void Add(int x,int y,int z){
next[++tot]=first[x]; first[x]=tot; end[tot]=y; value[tot]=z;
next[++tot]=first[y]; first[y]=tot; end[tot]=x; value[tot]=z;
}
void Dfs(int x,int fa,int &Ans){
size[x]=1;
for (int k=first[x],v;v=end[k],k;k=next[k]){
if (v==fa) continue;
if (mark[v]) continue;
Dist[v]=Dist[x]+value[k];
dep[v]=dep[x]+1;
if (Dist[v]<=K)
if (f[K-Dist[v]]==T)
Ans=min(Ans,P[K-Dist[v]]+dep[v]);
Q.push(v);
Dfs(v,x,Ans);
size[x]+=size[v];
}
}
void Search(int x,int fa,int o){
maxx[x]=o-size[x];
for (int k=first[x],v;v=end[k],k;k=next[k]){
if (v==fa) continue;
if (mark[v]) continue;
Search(v,x,o);
maxx[x]=max(maxx[x],size[v]);
}
if (maxx[x]<maxx[Focus]||(!Focus)) Focus=x;
}
int QAns(int x){
mark[x]=1;
P[0]=0;
f[0]=++T;
for (;!Q.empty();)
Q.pop();
int Ans=INF;
for (int k=first[x],v;v=end[k],k;k=next[k]){
if (mark[v]) continue;
Dist[v]=value[k];
dep[v]=1;
if (Dist[v]<=K)
if (f[K-Dist[v]]==T)
Ans=min(Ans,P[K-Dist[v]]+dep[v]);
Q.push(v);
Dfs(v,x,Ans);
for (;!Q.empty();){
int u=Q.front();
Q.pop();
if (Dist[u]<=K)
if (f[Dist[u]]!=T||P[Dist[u]]>dep[u]){
f[Dist[u]]=T;
P[Dist[u]]=dep[u];
}
}
}
for (int k=first[x],v;v=end[k],k;k=next[k]){
if (mark[v]) continue;
Focus=0;
Search(v,x,size[v]);
Ans=min(Ans,QAns(Focus));
}
return Ans;
}
int main(){
scanf("%d%d",&N,&K);
for (int i=1;i<N;++i){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
++x; ++y;
Add(x,y,z);
}
int a=INF;
Dfs(1,0,a);
Search(1,0,size[1]);
int Ans=QAns(Focus);
if (Ans!=INF) printf("%d\n",Ans);
else printf("-1\n");
}
打法较奇葩，切勿吐槽。。。
评论 (0)
