「BZOJ2599」[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
题解
这题有点怪的点分治。。。
我的做法也比较逗，就是开一个100W的数组t,t[i]表示权值为i的路径最少边数
找到重心分成若干子树后， 得出一棵子树的所有点到根的权值和x，到根a条边，用t[k-x]+a更新答案，全部查询完后
然后再用所有a更新t[x]
这样可以保证不出现点分治中的不合法情况
把一棵树的所有子树搞完后再遍历所有子树恢复T数组，如果用memset应该会比较慢
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<map> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,K,cnt,sum,root,ans; int t[1000005],last[200005],son[200005],f[200005],dis[200005],d[200005]; bool vis[200005]; struct edge{int to,next,v;}e[400005]; void insert(int u,int v,int w) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w; } void getroot(int x,int fa) { son[x]=1;f[x]=0; for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa&&!vis[e[i].to]) { getroot(e[i].to,x); son[x]+=son[e[i].to]; f[x]=max(f[x],son[e[i].to]); } f[x]=max(f[x],sum-son[x]); if(f[x]<f[root])root=x; } void cal(int x,int fa) { if(dis[x]<=K)ans=min(ans,d[x]+t[K-dis[x]]); for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa&&!vis[e[i].to]) { d[e[i].to]=d[x]+1; dis[e[i].to]=dis[x]+e[i].v; cal(e[i].to,x); } } void add(int x,int fa,bool flag) { if(dis[x]<=K) { if(flag)t[dis[x]]=min(t[dis[x]],d[x]); else t[dis[x]]=inf; } for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa&&!vis[e[i].to]) add(e[i].to,x,flag); } void work(int x) { vis[x]=1;t[0]=0; for(int i=last[x];i;i=e[i].next) if(!vis[e[i].to]) { d[e[i].to]=1;dis[e[i].to]=e[i].v; cal(e[i].to,0); add(e[i].to,0,1); } for(int i=last[x];i;i=e[i].next) if(!vis[e[i].to]) add(e[i].to,0,0); for(int i=last[x];i;i=e[i].next) if(!vis[e[i].to]) { root=0;sum=son[e[i].to]; getroot(e[i].to,0); work(root); } } int main() { n=read();K=read(); for(int i=1;i<=K;i++)t[i]=n; for(int i=1;i<n;i++) { int u=read(),v=read(),w=read(); u++;v++; insert(u,v,w); } ans=sum=f[0]=n; getroot(1,0); work(root); if(ans!=n)printf("%d\n",ans); else puts("-1"); return 0; } |
计数器 9854575
OI 课件=>
OI 课件=>
为什么“这样可以保证不出现点分治中的不合法情况”？？？
一棵一棵子树来咯，我写的不合法情况指的是起始点均在同一个子树内，路径经过根的情况