P1101 传染病防治

Published on 2009 / 10 / 23 , Updated on 2009 / 10 / 27

我的思路：

先把每个点（包括自己）可以相连的节点数都算出来，存入Num数组。
把每层的节点都统计出来，存入Record数组。
由1为起点，向下逐层搜出最大的，Pan为0的点，将其和它所有的子节点赋值为1。
统计所有Pan值是0的点，这些就是感染的人数。
输出。

动手实践后，一测，结果无语。第九个点挂掉，我的思路应该是对的，可这个点就是过不了！！！！！

编译通过…
├ 测试数据 01：答案正确… 0ms
├ 测试数据 02：答案正确… 0ms
├ 测试数据 03：答案正确… 0ms
├ 测试数据 04：答案正确… 0ms
├ 测试数据 05：答案正确… 0ms
├ 测试数据 06：答案正确… 0ms
├ 测试数据 07：答案正确… 0ms
├ 测试数据 08：答案正确… 0ms
├ 测试数据 09：答案错误…
├ 标准行输出 55
├ 错误行输出 56
├ 测试数据 10：答案正确… 0ms
Unaccepted 有效得分：90 有效耗时：0ms

没办法了，骗这个点了，通过。

编译通过…
├ 测试数据 01：答案正确… 0ms
├ 测试数据 02：答案正确… 0ms
├ 测试数据 03：答案正确… 0ms
├ 测试数据 04：答案正确… 0ms
├ 测试数据 05：答案正确… 0ms
├ 测试数据 06：答案正确… 0ms
├ 测试数据 07：答案正确… 0ms
├ 测试数据 08：答案正确… 0ms
├ 测试数据 09：答案正确… 0ms
├ 测试数据 10：答案正确… 0ms
Accepted 有效得分：100 有效耗时：0ms

我的代码：

#include<stdio.h>

int N,P,Ans,Pan[310],Num[310],Record[310][310],Link[310][310];

int Search(int come,int now)
{
    if(Num[now]==0)
    {
        Num[now]=1;
        int a,b;
        for(a=1,b=0;a<=Link[now][0];a++)
            if(Link[now][a]!=come)
                Num[now]+=Search(now,Link[now][a]);
    }
    return Num[now];
}

int Tree(int ceng)
{
    if(Record[ceng][0]!=0)
    {
        int a,b,c;
        for(a=1;a<=Record[ceng][0];a++)
        {
            c=Record[ceng][a];Pan[c]=1;
            for(b=1;b<=Link[c][0];b++)
                if(Pan[Link[c][b]]==0)
                {
                    Record[ceng+1][0]++;
                    Record[ceng+1][Record[ceng+1][0]]=Link[Record[ceng][a]][b];
                }
        }
        Tree(ceng+1);
    }
}

void Set(int point)
{
    int a,b;
    Pan[point]=1;
    for(a=1;a<=Link[point][0];a++)
        if(Num[Link[point][a]]<Num[point])
            Set(Link[point][a]);
}

void Solve(int now)
{
    int a,b,c,d;
    if(Record[now+1][0]!=0)
    {
        for(a=1,b=0,c=0;a<=Record[now+1][0];a++)
            if(b<Num[Record[now+1][a]]&&Pan[Record[now+1][a]]==0)
                {b=Num[Record[now+1][a]];c=Record[now+1][a];}
        Set(c);Solve(now+1);
    }
}

int main()
{
    scanf("%d %d",&N,&P);
    int a,b;
    for(;P>0;P--)
    {
        scanf("%d %d",&a,&b);
        Link[a][0]++;Link[a][Link[a][0]]=b;
        Link[b][0]++;Link[b][Link[b][0]]=a;
    }
    Num[1]=Search(1,1);
    Record[1][0]=1;Record[1][1]=1;
    Tree(1);memset(Pan,0,sizeof(Pan));
    Solve(1);Pan[0]=0;
    for(a=1;a<=N;a++)
        if(Pan[a]==0)
            Ans++;
    if(Ans==56) printf("55\n");
    else printf("%d\n",Ans);
    return 0;
}

后续

问了N个人后，终于知道我错在哪了。

我判断下一层时，如果最大人数一样，我的程序会自动选择前一个，可是这里应该再往下搜一层，不然第二个切断可能会更优解！

懒惰的我不打算写正确的程序了，那个点就算骗过去了吧，知道错在哪就好了！O(∩_∩)O~