链接：https://www.luogu.org/problemnew/show/P4149

题目描述

给一棵树，每条边有权。求一条简单路径，权值和等于 KK ，且边的数量最小。

输入输出格式

输入格式：

 

第一行：两个整数 n,kn,k 。

第二至 nn 行：每行三个整数，表示一条无向边的两端和权值 (注意点的编号从 00 开始)。

 

输出格式：

 

一个整数，表示最小边数量。

如果不存在这样的路径，输出 -1−1 。

 

输入输出样例

输入样例#1： 

4 30 1 11 2 21 3 4

输出样例#1： 

2

说明

n≤200000,K≤1000000 。

 

题解：点分， 统计经过中心长度为k且边数最少的路径，对每条路径记录属于哪棵子树，一个子树不能合并，不合法；

注意统计时的左右端点，zjj同学帮我调试了好久

还有，洛谷上不开O2要RE？

// luogu-judger-enable-o2#include
      
       #include
       
        #include
        
         using namespace std;const int M = 200005, K = 1000001;struct ST{
    int dis, id, les;}tong[M];bool cmp(ST a, ST b){    return a.dis < b.dis;}int n, tot, cnt, Ans = M, k, root, sum, h[M], siz[M], dis[M], f[M], dep[M];bool vis[M];struct edge{
    int v, nxt, w;}G[M<<1];void add(int u, int v, int w){    G[++tot].v = v; G[tot].w = w; G[tot].nxt = h[u]; h[u] = tot;}void init(){    memset(vis, 0, sizeof(vis));    memset(h, 0, sizeof(h));    tot = 0; Ans = K; sum = 0;}void getroot(int u, int fa){    siz[u] = 1; f[u] = 0;    for(int i = h[u]; i; i = G[i].nxt){        int v = G[i].v;        if(vis[v] || v == fa)continue;        getroot(v, u);        siz[u] += siz[v];        f[u] = max(f[u], siz[v]);    }    f[u] = max(f[u], sum - siz[u]);    if(f[u] < f[root]) root = u;     }void getdeep(int u, int fa, int zx){    tong[++cnt].dis = dis[u];    tong[cnt].id = zx;    tong[cnt].les = dep[u];    for(int i = h[u]; i; i = G[i].nxt){        int v = G[i].v;        if(vis[v] || v == fa)continue;        dis[v] = dis[u] + G[i].w;        dep[v] = dep[u] + 1;        if(zx == -1)zx = u;            getdeep(v, u, zx);        }}void cal(int u, int ret){    dis[u] = ret;    dep[u] = 0;    cnt = 0;     tong[++cnt].dis = dis[u];    tong[cnt].id = u;    tong[cnt].les = 0;    for(int i = h[u]; i; i = G[i].nxt){        int v = G[i].v;        if(vis[v])continue;        dis[v] = dis[u] + G[i].w;        dep[v] = dep[u] + 1;        getdeep(v, u, v);            }    sort(tong+1, tong+1+cnt, cmp);            int lf = 1, rg = cnt;    while(lf < rg){        while(tong[lf].dis + tong[rg].dis < k && lf <= cnt)lf++;        while(tong[lf].dis + tong[rg].dis > k && rg >= 1)rg--;        if(lf >= cnt || rg <= 1 || lf >= rg)break;        int llf = lf, rrg = rg;        if(tong[lf].dis + tong[rg].dis == k){            while(tong[llf].dis == tong[lf].dis && llf <= cnt)llf++;            while(tong[rrg].dis == tong[rg].dis && rrg >= 1)rrg--;            for(int i = lf; i < llf; i++)                for(int j = rrg+1; j <= rg; j++)                    if(tong[i].id != tong[j].id)                        Ans = min(Ans, tong[i].les + tong[j].les);            lf = llf, rg = rrg;            }            }    }void solve (int u){    cal(u, 0);    vis[u] = 1;    for(int i = h[u]; i; i = G[i].nxt){        int v = G[i].v;        if(vis[v])continue;        sum = siz[v];        getroot(v, root = 0);        solve(root);    }}int main(){    f[0] = 1e9;    scanf("%d%d", &n, &k);    for(int i = 1; i < n; i++){        int u, v, w;        scanf("%d%d%d", &u, &v, &w);        add(u + 1, v + 1, w); add(v + 1, u + 1, w);    }    sum = n;    getroot(1, 0);        solve(root);    if(Ans == M)printf("-1\n");    else printf("%d\n", Ans);}
        
       
      

 

 

这几天没调出一道程序，都是zjj同学帮我的，怎么感觉代码水平越学越烂？

2018-08-15