NC51143. Race
描述
给一棵树,每条边有权.求一条简单路径,权值和等于K,且边的数量最小.
输入描述
第一行 两个整数 n, k 第二..n行 每行三个整数 表示一条无向边的两端和权值 (注意点的编号从0开始)
输出描述
一个整数 表示最小边数量 如果不存在这样的路径 输出-1
示例1
输入:
4 3 0 1 1 1 2 2 1 3 4
输出:
2
NC51143. Race
描述
输入描述
第一行 两个整数 n, k 第二..n行 每行三个整数 表示一条无向边的两端和权值 (注意点的编号从0开始)
输出描述
一个整数 表示最小边数量 如果不存在这样的路径 输出-1
示例1
输入:
4 3 0 1 1 1 2 2 1 3 4
输出:
2
C++(g++ 7.5.0) 解法, 执行用时: 513ms, 内存消耗: 29744K, 提交时间: 2022-08-09 13:14:38
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <iostream>
#include <cstdlib>
using namespace std;
#define N 300505
#define ll long long
struct node
{
int to,next,val;
}e[N<<1];
int siz[N],dep[N],ans=1<<30,v[N*5],rot,sum,vis[N],mx[N],head[N],cnt,K,n;
ll dis[N];
void add(int x,int y,int z)
{
e[cnt].to=y;
e[cnt].next=head[x];
e[cnt].val=z;
head[x]=cnt++;
return ;
}
void get_root(int x,int from)
{
siz[x]=1;mx[x]=0;
for(int i=head[x];i!=-1;i=e[i].next)
{
int to1=e[i].to;
if(!vis[to1]&&to1!=from)
{
get_root(to1,x);
siz[x]+=siz[to1];
mx[x]=max(siz[to1],mx[x]);
}
}
mx[x]=max(mx[x],sum-siz[x]);
if(mx[x]<mx[rot])rot=x;
}
void insert(int x,int from)
{
if(dis[x]<=K)v[dis[x]]=min(v[dis[x]],dep[x]);
for(int i=head[x];i!=-1;i=e[i].next)
{
int to1=e[i].to;
if(!vis[to1]&&to1!=from)
{
insert(to1,x);
}
}
}
void clear(int x,int from)
{
if(dis[x]<=K)v[dis[x]]=1<<30;
for(int i=head[x];i!=-1;i=e[i].next)
{
int to1=e[i].to;
if(!vis[to1]&&to1!=from)
{
clear(to1,x);
}
}
}
void calc(int x,int from)
{
if(dis[x]<=K)ans=min(ans,dep[x]+v[K-dis[x]]);
for(int i=head[x];i!=-1;i=e[i].next)
{
int to1=e[i].to;
if(to1!=from&&!vis[to1])
{
dep[to1]=dep[x]+1;
dis[to1]=dis[x]+e[i].val;
calc(to1,x);
}
}
}
void dfs(int x)
{
vis[x]=1;v[0]=0;
for(int i=head[x];i!=-1;i=e[i].next)
{
int to1=e[i].to;
if(!vis[to1])
{
dep[to1]=1,dis[to1]=e[i].val;
calc(to1,0);
insert(to1,0);
}
}
for(int i=head[x];i!=-1;i=e[i].next)
{
int to1=e[i].to;
if(!vis[to1])
{
clear(to1,0);
}
}
for(int i=head[x];i!=-1;i=e[i].next)
{
int to1=e[i].to;
if(!vis[to1])
{
sum=siz[to1];rot=0;
get_root(to1,0);
dfs(rot);
}
}
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&K);
for(int i=1;i<n;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x+1,y+1,z);
add(y+1,x+1,z);
}
for(int i=1;i<=K;i++)v[i]=1<<30;
mx[0]=sum=n;
get_root(1,0);
dfs(rot);
if(ans==1<<30)
{
puts("-1");
return 0;
}
printf("%d\n",ans);
return 0;
}
C++ 解法, 执行用时: 241ms, 内存消耗: 22036K, 提交时间: 2021-08-01 11:41:04
#include <iostream>
#include <cstring>
#include <algorithm>
#include <climits>
using namespace std;
const int maxn=200020,maxk=1000100;
int n,k,el,head[maxn],to[maxn*2],w[maxn*2],nxt[maxn*2];
int rt,tot,sz[maxn],son[maxn],mine[maxk],ans=INT_MAX,dis1[maxn],dis2[maxn],dl;
bool vis[maxn];
inline void add(int u,int v,int w_)
{
to[++el]=v;w[el]=w_;nxt[el]=head[u];head[u]=el;
}
void getrt(int u,int f)
{
sz[u]=1;son[u]=0;
for(int i=head[u];i;i=nxt[i]){
if(to[i]==f || vis[to[i]])
continue;
getrt(to[i],u);
sz[u]+=sz[to[i]];son[u]=max(son[u],sz[to[i]]);
}
son[u]=max(son[u],tot-sz[u]);
if(son[u]<son[rt]) rt=u;
}
void getdis(int u,int f,int d1,int d2)
{
if(d1>k)
return;
dis1[++dl]=d1;dis2[dl]=d2;
for(int i=head[u];i;i=nxt[i]){
if(to[i]==f || vis[to[i]])
continue;
getdis(to[i],u,d1+w[i],d2+1);
}
}
void getans(int u)
{
mine[0]=0;dl=0;
for(int i=head[u];i;i=nxt[i])
{
if(vis[to[i]])
continue;
int pdl=dl;
getdis(to[i],u,w[i],1);
for(int j = pdl + 1 ; j <= dl ; j ++)
ans=min(ans,mine[k-dis1[j]]+dis2[j]);
for(int j = pdl + 1 ; j <= dl ; j ++)
mine[dis1[j]]=min(mine[dis1[j]],dis2[j]);
}
for(int i = 1 ; i <= dl ; i++)
mine[dis1[i]]=1e9;
}
void getall(int u){
vis[u]=true;
getans(u);
for(int i=head[u];i;i=nxt[i])
{
if(vis[to[i]])
continue;
tot=sz[to[i]];
rt=0;
getrt(to[i],u);
getall(rt);
}
}
int main(){
scanf("%d%d",&n,&k);
for(int i = 1 ; i < n ; i ++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
u++,v++;
add(u,v,w);add(v,u,w);
}
son[0]=(tot=n)+1;
getrt(1,0);
memset(mine,0x3f,sizeof(mine));
getall(rt);
printf("%d\n",ans>=n?-1:ans);
}