BZOJ 2599: [IOI2011]Race 点分治题解

122 阅读 0 评论 81 点赞

我是靠谱客的博主包容黑猫，这篇文章主要介绍BZOJ 2599: [IOI2011]Race 点分治题解，现在分享给大家，希望可以做个参考。

Time Limit: 70 Sec Memory Limit: 128 MB
Submit: 3811 Solved: 1129

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

Sample Output

HINT

Source

貌似是IOI题？？？

题解：

貌似我们点分一下，然后two-pointer指指，用一个数组来存当边数为i的时候是否有满足边权和为k的情况，然后最后for一边找出最小的i
就可以ac了

复制代码

#include<cstdio>
#include<vector>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=200000+1000;
struct Line{int to,nxt,flow;}line[MAXN*2];
int mx[MAXN],ans[MAXN],vis[MAXN],root,dis[MAXN],dep[MAXN],sz[MAXN],n,k,sum,head[MAXN],tail;
void add_line(int from,int to,int flow){line[++tail].to=to;line[tail].flow=flow;line[tail].nxt=head[from];head[from]=tail;}
struct A{
    int dis,dep;
    bool operator <(const A &x) const{return dis<x.dis;}
}a[MAXN];
void getroot(int u,int fa){
    mx[u]=0;sz[u]=1;
    for(register int i=head[u];i;i=line[i].nxt){
        int v=line[i].to;
        if(vis[v]||v==fa) continue;
        getroot(v,u);
        sz[u]+=sz[v];
        mx[u]=max(mx[u],sz[v]);
    }
    mx[u]=max(mx[u],sum-mx[u]);
    if(mx[u]<mx[root]) root=u;
}
void getdeep(int u,int fa){
    a[++tail]=(A){dis[u],dep[u]};
    for(register int i=head[u];i;i=line[i].nxt){
        int v=line[i].to;
        if(vis[v]||v==fa) continue;
        dis[v]=dis[u]+line[i].flow;
        dep[v]=dep[u]+1;
        getdeep(v,u);
    }
}
void cal(int u,int ddis,int ddep,int delta){
    dis[u]=ddis;dep[u]=ddep;tail=0;
    getdeep(u,0);
    sort(a+1,a+tail+1);
    int l=1,r=tail;
    while(l<=r){
        while(l<r&&a[l].dis+a[r].dis>k)--r;
        int i=r;
        while(a[l].dis+a[i].dis==k) ans[a[l].dep+a[i].dep]+=delta,--i;
        l++;
    }
}
void solve(int u){
    cal(u,0,0,1);
    vis[u]=1;
    for(register int i=head[u];i;i=line[i].nxt){
        int v=line[i].to;
        if(vis[v]) continue;
        cal(v,line[i].flow,1,-1);
        sum=sz[v],root=0;
        getroot(v,0);
        solve(root);
    }
}
int main(){
    scanf("%d%d",&n,&k);
    for(register int i=1;i<=n-1;i++){int u,v,w;
        scanf("%d%d%d",&u,&v,&w);add_line(u+1,v+1,w);add_line(v+1,u+1,w);
    }
    sum=n;root=0,mx[0]=0x7ffffff;
    getroot(1,0);
    solve(root);
    for(register int i=1;i<n;i++)
        if(ans[i]){printf("%dn",i);return 0;}
    printf("-1n");
    return 0;
}

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
#include<cstdio>
#include<vector>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=200000+1000;
struct Line{int to,nxt,flow;}line[MAXN*2];
int mx[MAXN],ans[MAXN],vis[MAXN],root,dis[MAXN],dep[MAXN],sz[MAXN],n,k,sum,head[MAXN],tail;
void add_line(int from,int to,int flow){line[++tail].to=to;line[tail].flow=flow;line[tail].nxt=head[from];head[from]=tail;}
struct A{
    int dis,dep;
    bool operator <(const A &x) const{return dis<x.dis;}
}a[MAXN];
void getroot(int u,int fa){
    mx[u]=0;sz[u]=1;
    for(register int i=head[u];i;i=line[i].nxt){
        int v=line[i].to;
        if(vis[v]||v==fa) continue;
        getroot(v,u);
        sz[u]+=sz[v];
        mx[u]=max(mx[u],sz[v]);
    }
    mx[u]=max(mx[u],sum-mx[u]);
    if(mx[u]<mx[root]) root=u;
}
void getdeep(int u,int fa){
    a[++tail]=(A){dis[u],dep[u]};
    for(register int i=head[u];i;i=line[i].nxt){
        int v=line[i].to;
        if(vis[v]||v==fa) continue;
        dis[v]=dis[u]+line[i].flow;
        dep[v]=dep[u]+1;
        getdeep(v,u);
    }
}
void cal(int u,int ddis,int ddep,int delta){
    dis[u]=ddis;dep[u]=ddep;tail=0;
    getdeep(u,0);
    sort(a+1,a+tail+1);
    int l=1,r=tail;
    while(l<=r){
        while(l<r&&a[l].dis+a[r].dis>k)--r;
        int i=r;
        while(a[l].dis+a[i].dis==k) ans[a[l].dep+a[i].dep]+=delta,--i;
        l++;
    }
}
void solve(int u){
    cal(u,0,0,1);
    vis[u]=1;
    for(register int i=head[u];i;i=line[i].nxt){
        int v=line[i].to;
        if(vis[v]) continue;
        cal(v,line[i].flow,1,-1);
        sum=sz[v],root=0;
        getroot(v,0);
        solve(root);
    }
}
int main(){
    scanf("%d%d",&n,&k);
    for(register int i=1;i<=n-1;i++){int u,v,w;
        scanf("%d%d%d",&u,&v,&w);add_line(u+1,v+1,w);add_line(v+1,u+1,w);
    }
    sum=n;root=0,mx[0]=0x7ffffff;
    getroot(1,0);
    solve(root);
    for(register int i=1;i<n;i++)
        if(ans[i]){printf("%dn",i);return 0;}
    printf("-1n");
    return 0;
}