问题描述:

简单来说,就是给你一棵树,在直径上找一个长度不超过s的链,使得偏心距最小。偏心距的定义为:树上到这条链最远的节点到这条链的距离。

输入:

包含n行: 第1行,两个正整数n和s。其中n为树网结点的个数,s为树网的核的长度的上界。
从第2行到第n行,每行给出3个用空格隔开的正整数,依次表示每一条边的两个端点编号和长度。

注:NOIP原题数据:n<=300,BZOJ加强数据:n<=500000

输出:

只有一个非负整数,为指定意义下的最小偏心距。

思路:

首先想NOIP数据范围的做法,因为我们找的链是在直径上。所以我们可以先处理出直径再暴力枚举直径上的链。因为链长要小于等于s,我们可以枚举一个端点,然后尽可能远的在链上找到另一个端点。这样我们就$O(n)$暴力枚举处理所有链,对于每一条链用一次dfs找出偏心距就OK了。

然后再考虑BZOJ加强版数据,枚举一个端点,然后尽可能远的在链上找到另一个端点。但是我们可以不需要对于每一条链都找出偏心距,我们可以利用直径的性质$O(n)$统一处理出答案。

代码:

$O(n^2)$暴力:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define MAXN 3005
#define INF 0x3f3f3f3f
using namespace std;

int n, s, root, cnt, ans=INF, ecc, head[MAXN], dis[MAXN], pre[MAXN];
bool vis[MAXN];

struct Edge {int next, to, dis;} edge[MAXN*2];

void addedge(int from, int to, int dis)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    head[from]=cnt;
}

void bfs(int root)
{
    queue<int> q;
    vis[root]=true; q.push(root);
    while(!q.empty())
    {
        int x=q.front(); q.pop();
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if(vis[to]) continue;
            pre[to]=x; vis[to]=true;
            dis[to]=dis[x]+edge[i].dis;
            q.push(to);
        }
    }
}

void getline()
{
    int maxdis=0;
    bfs(1);
    for(int i=1; i<=n; i++) if(dis[i]>maxdis) maxdis=dis[i], root=i;
    memset(vis, 0, sizeof(vis));
    memset(pre, 0, sizeof(pre));
    memset(dis, 0, sizeof(dis));
    bfs(root);
    maxdis=0;
    for(int i=1; i<=n; i++) if(dis[i]>maxdis) maxdis=dis[i], root=i;
}

void dfs(int x, int fa, int dis)
{
    ecc=max(ecc, dis);
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa || vis[to]) continue;
        dfs(to, x, edge[i].dis+dis);
    }
}

void solve()
{
    for(int x=root; x; x=pre[x])
    {
        int y=0, len=0; ecc=0;
        memset(vis, 0, sizeof(vis));
        for(int i=x; i; i=pre[i])
        {
            for(int j=head[i]; j; j=edge[j].next)
                if(edge[j].to==pre[i]) len+=edge[j].dis;
            y=i; vis[i]=true;
            if(len>s) break;
        }
        for(int i=x; ; i=pre[i])
        {
            dfs(i, 0, 0);
            if(i==y) break;
        }
        ans=min(ans, ecc);
    }
}

int main()
{
    scanf("%d%d", &n, &s);
    for(int i=1; i<n; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        addedge(x, y, z);
        addedge(y, x, z);
    }
    getline();
    solve();
    printf("%d\n", ans);
}

$O(n)$做法:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define LL long long
#define MAXN 500005

LL min(LL x, LL y) {if(x<y) return x; return y;}
LL max(LL x, LL y) {if(x<y) return y; return x;}

int n, s, lpnt, rpnt, cnt, head[MAXN], pre[MAXN];
LL  ans=1e18, dis[MAXN];
bool vis[MAXN];

struct Edge {int next, to; LL dis;} edge[MAXN*2];

void addedge(int from, int to, LL dis)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    head[from]=cnt;
}

void dfs(int x, int fa)
{
    pre[x]=fa;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa || vis[to]) continue;
        dis[to]=dis[x]+edge[i].dis;
        dfs(to, x);
    }
}

void getline()
{
    LL maxdis=0; dis[1]=0;
    dfs(1, 0);
    for(int i=1; i<=n; i++) if(dis[i]>maxdis) maxdis=dis[i], lpnt=i;
    maxdis=0; dis[lpnt]=0;
    dfs(lpnt, 0);
    for(int i=1; i<=n; i++) if(dis[i]>maxdis) maxdis=dis[i], rpnt=i;
}

void solve()
{
    int l=rpnt, r=rpnt;
    for(; l; l=pre[l])
    {
        while(pre[r] && dis[l]-dis[pre[r]]<=s) r=pre[r];
        ans=min(ans, max(dis[rpnt]-dis[l], dis[r]));
    }
    for(int i=rpnt; i; i=pre[i]) vis[i]=true;
    for(int i=rpnt; i; i=pre[i]) dis[i]=0, dfs(i, pre[i]);
    for(int i=1; i<=n; i++) ans=max(ans, dis[i]);
}

int main()
{
    scanf("%d%d", &n, &s);
    for(int i=1; i<n; i++)
    {
        int x, y; LL z;
        scanf("%d%d%lld", &x, &y, &z);
        addedge(x, y, z);
        addedge(y, x, z);
    }
    getline();
    solve(); 
    printf("%lld\n", ans);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注