A simple Blog for wyx I've been down the bottle hoping.
BZOJ 2599 [IOI2011]Race 点分治
发表于: | 分类: Oi | 评论:0 | 阅读:45

给一棵树,每条边有权.求一条简单路径,权值和等于K,且边的数量最小.N <= 200000, K <= 1000000

原理和poj 1741完全相同,就是这个东西一定在一个点为根的子树中
然后我们分治处理
讲一下这个的处理方法
对于一个根我们一棵子树一棵子树的扫。设对于之前 $i-1$ 棵子树,长度为$j$的最少边数为 $G[j]$ ,然后我们就可以用 $depth + G[K-dis[x]]$ 更新答案了
做完这个树之后我们可以再遍历一下这棵子树,把G数组更新

注意一个细节,一个分治结构复杂度正确的前提是在该层的操作至于该层的大小有关
也就是说你在这个根全做完需要清数组的时候不能memset
所以我们记录他的最大深度更新就行了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int inf = 0x3f3f3f3f;
const int N = 200000 + 5;
const int M = N << 1;
const int Maxn = 1000000+5;
using namespace std;

int head[N],n;

struct graph
{
    int next,to,val;
    graph () {}
    graph (int _next,int _to,int _val)
    :next(_next),to(_to),val(_val){}
}edge[M];

inline void add(int x,int y,int z)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x],y,z);
    head[x] = cnt;
    edge[++cnt] = graph(head[y],x,z);
    head[y] = cnt;
}

int T[Maxn],dis[N],F[N],k,root;
int size[N],depth[N],sum;
bool vis[N];

void DFS1(int x,int fa)
{
    size[x] = 1, F[x] = 0;
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to != fa && !vis[edge[i].to])
        {
            DFS1(edge[i].to,x);
            size[x] += size[edge[i].to];
            F[x] = max(F[x],size[edge[i].to]);
        }
    F[x] = max(F[x],sum - size[x]);
    root = F[x] < F[root] ? x : root;
}

int ans = inf;

void DFS2(int x,int fa)
{
    if(dis[x] <= k) ans = min(ans,depth[x] + T[k - dis[x]]);
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to != fa && !vis[edge[i].to])
        {
            depth[edge[i].to] = depth[x] + 1;
            dis[edge[i].to] = dis[x] + edge[i].val;
            DFS2(edge[i].to,x);
        }
}

void init(int x,int fa,int opt)
{
    if(dis[x] <= k)
    {
        if(opt) T[dis[x]] = min(T[dis[x]],depth[x]);
        else T[dis[x]] = inf;
    }
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to != fa && !vis[edge[i].to])
            init(edge[i].to,x,opt);
}

void solve(int x)
{
    vis[x] = 1; T[0] = 0;
    for(int i=head[x];i;i=edge[i].next)
        if(!vis[edge[i].to])
        {
            depth[edge[i].to] = 1;
            dis[edge[i].to] = edge[i].val;
            DFS2(edge[i].to,x);
            init(edge[i].to,x,1);
        }
    for(int i=head[x];i;i=edge[i].next)
        if(!vis[edge[i].to])
            init(edge[i].to,x,0);
    for(int i=head[x];i;i=edge[i].next)
        if(!vis[edge[i].to])
        {
            sum = size[edge[i].to],root = 0;
            DFS1(edge[i].to,x);
            solve(root);
        }
}

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<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int main()
{
    n = read(), k = read();
    for(int i=1;i<=k;++i) T[i] = n;
    for(int i=1,x,y,z;i<n;++i)
    {
        x = read() + 1, y = read() + 1, z = read();
        add(x,y,z);
    }
    sum = n ; F[0] = inf;
    root = 0;
    DFS1(1,1);
//  cout << root << endl;
    solve(root);
    printf("%d\n" , ans < n ? ans : -1);
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP