【AtCoder1981】Shorten Diameter（图论思维）

72 阅读 0 评论 48 点赞

我是靠谱客的博主专一羊，最近开发中收集的这篇文章主要介绍【AtCoder1981】Shorten Diameter（图论思维），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意

给一棵树，要求删去最少的点，使得树联通且直径小于等于K
(N<=2000)

题解

简单的问题也容易想复杂。

对于K为偶数，枚举一个点，将距离此点>K/2的全部删掉即可满足条件，取删点数最小值。
对于K为奇数，枚举一条边，树被此边分为两棵，将其深度>(K-1)/2的全部删掉，取删点数最小值。

考试时想复杂了：把直径求出，然后试图从直径两头删点，包含大量特殊情况。。。死路一条

代码

#include<cstdio>
#include<vector>
using namespace std;
const int MAXN=2005;

int N,K;
vector<int> adj[MAXN];
int dep[MAXN],fa[MAXN],cnt;

void dfs(int u,int f,int lim)
{
    for(int i=0;i<(int)adj[u].size();i++)
    {
        int v=adj[u][i];
        if(v!=f)
        {
            dep[v]=dep[u]+1;
            if(dep[v]>lim)
                cnt++;
            dfs(v,u,lim);
        }
    }
}

int main()
{
    scanf("%d%d",&N,&K);
    for(int i=1;i<N;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int ans=0x3F3F3F3F;
    if(K%2==0)
    {
        for(int i=1;i<=N;i++)
        {
            cnt=0;
            dep[i]=0;dfs(i,0,K/2);
            ans=min(ans,cnt);
        }
    }
    else
    {
        for(int i=1;i<=N;i++)
            for(int j=0;j<(int)adj[i].size();j++)
            {
                cnt=0;
                dep[i]=0;dfs(i,adj[i][j],K/2);
                dep[adj[i][j]]=0;dfs(adj[i][j],i,K/2);
                ans=min(ans,cnt);
            }
    }

    printf("%dn",ans);

    return 0;
}