BDZNH
0%

NOIP 2015 信息传递

Posted on Edited on
Symbols count in article: Reading time ≈ NaN:aN

初探图论，这本来是大一就该学的，没想到拖到这个假期，感觉好懒啊。
尝试做了一下NOIP 2015 day1 的信息传递，整理如下。

题目

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
    int n,i,j=0;
    cin>>n;
    int circle[n+2]={0},status[n+2]={0},via[n+2]={0},flag[n+2]={0};//circle用来存储输入的数据，status用来记录i个人有几个人会告诉他信息，via用来记录某个人是否被告诉过信息
    for( i = 1 ; i <= n ; i++ )
    {
        cin>>circle[i];
        status[circle[i]]++;
    }
    for( i = 1 ; i <=  n; i++ )
    {
        if(status[i]==0)
        {
            flag[j++]=i;
            via[i]=1;
        }
    }
    for( i = 0 ; i < j ; i++ )
    {
        status[circle[flag[i]]]--;
        if(status[circle[flag[i]]]==0)
        {
            flag[j++]=circle[flag[i]];
            via[circle[flag[i]]]=1;
        }
    }
    int ans=n,temp;
    for( i = 1 ; i <= n ; i++ )
    {
        if( via[i]==0 && circle[i]!=0 )
        {
            via[i]=1;
            temp=1;
            j=circle[i];
            while(!via[j])
            {
                via[j]=1;
                j=circle[j];
                temp++;
            }
            if(temp<ans)
                ans=temp;
        }
    }
    printf("%d",ans);
    return 0;
}

解析

题意说明

代码大量参考了此文章
文中的没有给出详细解题信息，我看了之后整理了一下。
文中有这样一句话

其实这道题题意非常明确，就是让我们寻找一个最小环的长度，怎么求呢？也很简单，先把入度为0的点删除，然后把这个点指向的点的入度-1，如果入度为0，也删去，这样就只保留有用的点，那么从任意一个点开始，用vis数组记录是否被访问过，访问到一个新节点就累加计数器，然后就做出来了.bfs和dfs都可以.

把样例输入数据变成图，就成了这样：

从图中可以看到，第一个人讲自己所知道的信息告诉第二个人，第二个人告诉第四个人，第三个人告诉第二个人，第四个人告诉第三个人，第五个人告诉第一个人。这样，仔细一看，2绝对不可能从1处获得自己的生日(游戏结束条件)

很容易看出，2将自己的生日告诉3，3告诉4，4告诉2，2获得了自己的生日，游戏结束，对于3和4来说也同样是这样。

所以，这个题简短来说，就是找到图中的最小环。

解题思路

首先，由于5—>1—>2并不构成圈，所以2不可能从1处获得自己的信息，所以干脆将5–>1–>2这条路去掉，这样，只需要统计形成圈的有几个人就行了，若有多个圈，找出最小的圈就好。

代码分析

存储数据，计算权值

1
2
3
4
5
for( i = 1 ; i <= n ; i++ )
{
    cin>>circle[i];
    status[circle[i]]++;
}

这一段意思很明显，输入数据，然后，记录每个人有几个人告诉他信息

找到权值为0的人

权值为0，也就是示范数据中的5号，没有任何人将自己的信息告诉他

1
2
3
4
5
6
7
8
for( i = 1 ; i <=  n; i++ )
{
    if(status[i]==0)
    {
        flag[j++]=i;
        via[i]=1;
    }
}

flag用于标记权值为0的人的编号

去除权值为0的点

1
2
3
4
5
6
7
8
9
for( i = 0 ; i < j ; i++ )
{
    status[circle[flag[i]]]--;//去掉某个权值为0的点之后，讲它所指向的人的权值减1
    if(status[circle[flag[i]]]==0)//若此人的权值减1之后，其权值为0，就将他的编号标记一下，同时更新j(x循环结束条件)的值
    {
        flag[j++]=circle[flag[i]];
        via[circle[flag[i]]]=1;
    }
}

计算圈的成员数目，找到最小的圈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int ans=n,temp;
for( i = 1 ; i <= n ; i++ )
{
    if( via[i]==0 && circle[i]!=0 )
    {
        via[i]=1;
        temp=1;
        j=circle[i];
        while(!via[j])
        {
            via[j]=1;
            j=circle[j];
            temp++;
        }
        if(temp<ans)
            ans=temp;
    }
}

一点点小总结

可能我的解析说得也并不比原文详细多少，实际上我是跟着代码一步一步调试，才看懂原文的代码的。

然后，我剔除了原文的队列，使用了一个数组代替，导致我不得不更新数组的有效长度，也就是文中的j值。反而让代码变得更加难以理解。不过，也照顾了一下不知道队列的小伙伴。
然后，原文使用了

1
memset(to, 0, sizeof(to));

来将数组清零，有时候，会忘记这个函数的用法，所以我用了下面的办法

1
int a[100]={0};

这样，只要初始化数组的第一个元素为0，数组的其他元素会全都变成0。

生命重在折腾