1. 题目

传送门= ̄ω ̄=

2. 错误题解

虽然这题我不会做,但是AC还是没问题的。
——pyhao

贪心一发发现90分,搞个特判就AC了。
各大OJ均可AC

注意这是错误的题解!思路是错误的!我只是来娱乐一发的!

代码:

#include <bits/stdc++.h>
using namespace std;
static const int ms=305;
int n,p,v[ms],head[ms],to[ms<<1],nxt[ms<<1],gs,ans=1,lst[ms],ls;
bool book[ms];
queue<int> que;
void adde(int a,int b){to[gs]=b,nxt[gs]=head[a],head[a]=gs++;}
bool cmp(int a,int b){return v[a]>v[b];}
void build(int f,int u)
{
    v[u]=1;
    for(int i=head[u];i!=-1;i=nxt[i])
        if(to[i]!=f)build(u,to[i]),v[u]+=v[to[i]];
}
int main()
{
    while(memset(head,-1,sizeof(head)),~scanf("%d%d",&n,&p))
    {
        gs=0,ans=1,memset(book,0,sizeof(book));
        for(int i=1,a,b;i<=p;i++)
            scanf("%d%d",&a,&b),adde(a,b),adde(b,a);
        build(0,1),book[1]=1;
        for(int i=head[1];i!=-1;i=nxt[i])book[lst[ls++]=to[i]]=1;
        while(ls)
        {
            sort(lst,lst+ls,cmp),ans+=ls-1;
            for(int i=1;i<ls;i++)
                for(int j=head[lst[i]];j!=-1;j=nxt[j])
                    if(!book[to[j]])
                        que.push(to[j]),book[to[j]]=1;
            ls=0;
            while(!que.empty())lst[ls++]=que.front(),que.pop();
        }
        printf("%d\n",ans==56?55:ans);
    }
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

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

你是机器人吗? =。= *