Loading...

洛谷P2279 [HNOI2003]消防局的设立

check评论:0 条 remove_red_eye浏览量:394 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-10-10

所有人都会树形$dp$,只有我只会$dfs$qaq,我菜死了

我们先把每个点的深度搞出来,这种题贪心就可以啦qwq

#include <bits/stdc++.h>
using namespace std;
int head[1010],tmp[1010],cnt,n,vis[1010],ans=0;
struct node
{
    int id,dep;
    bool operator<(const node&a)const
    {
        return dep>a.dep;
    }
}no[1010];
struct edge
{
    int next,to;
}e[2020];
void add(int u,int v)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(int u,int tp)
{
    vis[u]=tmp[u]=1;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(!tmp[v]&&tp>0)
        {
            dfs(v,tp-1);
        }
    }
    tmp[u]=0;
    return ;
}
int main()
{
    cin>>n;
    no[1].dep=1;
    no[1].id=1;
    for(int i=2;i<=n;i++)
    {
        int f;
        scanf("%d",&f);
        add(f,i);
        add(i,f);
        no[i].dep=no[f].dep+1;
        no[i].id=i;
    }
    sort(no+1,no+n+1);
    for(int i=1;i<=n;i++)
    {
        if(!vis[no[i].id])
        {
            ans++;
            dfs(no[i].id,4);
        }
    }
    cout<<ans;
}

POJ 1741 Tree chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名