A simple Blog for wyx I've been down the bottle hoping.
BZOJ 2097 Exercise 二分答案+树形dp+贪心
发表于: | 分类: Oi | 评论:0 | 阅读:52

题目大意:给定一棵树,可以删掉k条边,求删掉后森林中所有树直径的最大值的最小值

最大值的最小值,我们容易想到贪心
但是现在验证出现了一点小麻烦
我们可以利用树形$dp$维护处$f(i)$表示点在他的子树中经过他的最长的链
显然 $$f(i) = max{f(son[i])}$$
然后我们可以将一个点的 $f$ 排个序
我们就知道了最长链和次长链
贪心删掉最长链的,直到最长+次长 $<=$ 二分的 $ans$

时间复杂度 $O(nlog^2(n))$
理论上是会被卡一点,但是实际上由于每一次排序并不是都排,复杂度到不了上限
所以是对的

不明原因错了很多遍,重写之后就过了,感觉没啥差别……

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define N 100010
#define M N << 1
using namespace std;

int head[N];

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

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

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 n,s;
int ans;
int f[N],a[N];

void DFS(int x,int fa,int lmt)
{
    f[x] = 0;
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to!=fa)
            DFS(edge[i].to,x,lmt);
    int cnt = 0;
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to!=fa)
            a[++cnt] = f[edge[i].to] + 1;
    sort(a+1,a+cnt+1);
    while(cnt && a[cnt] + a[cnt-1] > lmt)
        cnt -- , ans ++ ;
    f[x] = a[cnt];
}

bool check(int mid)
{
    ans = 0;
    DFS(1,0,mid);
    return ans <= s;
}

int main()
{
    cin >> n >> s;
    for(int i=1;i<n;++i)
    {
        int x = read() , y = read();
        add(x,y);
    }
    int l = 1;
    int r = n;
    int ans = n;
    while(l<=r)
    {
        int mid = (l+r)>>1;
        if(check(mid))
            ans = mid , r = mid - 1 ;
        else l = mid + 1;
    }
    printf("%d\n",ans);
}
Title - Artist
0:00

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

TOP