UOJ Logo kb的博客

博客

364水题题解

2019-02-12 08:06:19 By kb

364水题题解

这道题是考试时候最水的一道题。

30分做法

n是小于等于5的,因此可以手动模拟啊qwq。暴力三十分到手。

另外30分做法

#include<cstdio>
using namespace std;
int main()
{
    printf("0");
}

好的,这三十分也到手了,是不是感觉很水。这时候你应该发现了,只要图是联通的,就不需要建立神圣城。

因此,只需要统计一下单点的数量,相信你们都会......

满分做法

#include<cstdio>
using namespace std;
#define kb 100010
bool bj[kb]; 
int main()
{
    int n, m, u, v, ans=0;
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d", &u, &v);
        bj[u]=bj[v]=1;
    }
    for(int i=1; i<=n; i++)
        if(!bj[i])    ans++;
    printf("%d", ans);
    return 0;
}

话说这道题考试的时候代码被卡掉了,只拿了四十分,但是这个思路确实很简单吧。

评论

NaCl
制杖 0xis 强行解释ing… 1) 一棵树(除非单点)不需要神圣城。第 1 层生命,第 2 层魔法,第 3 层生命,第 4 层魔法…即可。 2) 无向连通图总有至少一棵最小生成树。如果最小生成树的边足以传导生命和魔法,那么多出来的边是无意义的。(如果只用 QQ 就能保持联系,您会同时使用 QQ、Telegram、Freenode 吗?) 3) 因此,原图的所有分量(除非单点)均不需要神圣城。亦即神圣城数量等于单点数量。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。