Loading...

洛谷P2899 [USACO08JAN]手机网络Cell Phone Network

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

这道题好像是双倍经验啊

消防局的设立有点像是不是啊qwq

思路一模一样啊qwq

#include <bits/stdc++.h>
using namespace std;
int head[10010],cnt,vis[10010],m;
struct edge
{
    int next,to;
}e[20020];
struct node
{
    int id,dep;
    bool operator<(const node&a)const
    {
        return dep>a.dep;
    }
}n[10010];
void add(int u,int v)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void dfs1(int u,int fa)
{
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa)
        {
            continue;
        }
        n[v].dep=n[u].dep+1;
        dfs1(v,u);
    }
}
void dfs(int u,int fa,int k)
{
    vis[u]=1;
    if(k==0)
    {
        return ;
    }
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa)
        {
            continue;
        }
        dfs(v,u,k-1);
    }
}
int main()
{
    cin>>m;
    n[1].dep=1;
    n[m].id=m;
    for(int i=1;i<m;i++)
    {
        n[i].id=i;
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs1(1,0);
    sort(n+1,n+m+1);
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        if(!vis[n[i].id])
        {
            ans++;
            dfs(n[i].id,0,2);
        }
    }
    cout<<ans;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名