杭电ACM 1232 畅通工程

来源:转载

这个题大家一看到可能就会想到用并查集,高手们都用这种方法解决这个问题。像我,刚刚学习编程不久,还不知道什么是并查集,

所以我就自己写了个解决方法。

我的思路是  帮所有可以相通的城市化为一个城市群,称之为层。这个题的关键就是求出所有的层,添加最少的道路即为层数减一条。

从输入开始,如果这两个城在之前都没有城市可以通达,则化为一个新层,层数加一;若其中有一个城市出现,则把没有出现的城市化

为已经出现的那个城市所在的层;如果都出现了,它们所在的层不同则进行替换,注意这里的替换是替换所有的相同的层数,详细可见

相应的代码区。

本来我以为就对了,可是这个题貌似还有非法数据,

比如

3 1

5 6

像这样的输入,我的程序就会出错,我的程序跑出来的是2,可正确结果是1。不过我们的思路是对的。我们只需要在出现新层,出现之前

无道路可通达的新城市,和出现的城市所在的层不同处,增加一条语句“MinAdd --”MinAdd 初始化城市数减一。其原因是,每当有道路存在

时,我们就可以少修一道路。好了 说了这么多,应该懂了,不懂的话可以在联系我。

此题URL http://acm.hdu.edu.cn/showproblem.php?pid=1232

这是我自己写的非并查集代码,可能有点长,但同样效率不低。

#include "stdio.h"#include "string.h"

int
main()
{

    int
city,road,i,j,a,b,temp;
    int
CityRoad[1001],floor[1001];
    int
MinAdd,part,ans;
    while
(scanf("%d%d",&city,&road),city)
    {

        memset(CityRoad,0,sizeof(CityRoad));
        memset(floor,0,sizeof(floor));
        part = 0;
        MinAdd = city-1;
        for
(i = 0; i < road; i ++)
        {

            scanf("%d%d",&a,&b);
            if
(CityRoad[a] == 0 && CityRoad[b] == 0) //两个城市第一次出现是一个新层
            {
                part ++;
                floor[part] = part;//记录当前层数
                CityRoad[a] = part;//记录层数和标识此城市已有道路通达
                CityRoad[b] = part;//记录层数和标识此城市已有道路通达
                MinAdd--;
            }

            else

            {

                if
(CityRoad[a] == 0 && CityRoad[b] != 0)
                {

                    CityRoad[a] = CityRoad[b];
                    MinAdd--;
                }

                else if
(CityRoad[a] != 0 && CityRoad[b] == 0)
                {

                    CityRoad[b] = CityRoad[a];
                    MinAdd--;
                }

                else if
(CityRoad[a] != 0 && CityRoad[b] != 0)
                {

                    if
(floor[CityRoad[a]] > floor[CityRoad[b]])
                    {

                        temp = floor[CityRoad[a]];   
                        for
(j = 1; j < part + 1; j ++)
                        {

                            if
(floor[j] == temp)
                            {

                                floor[j] =  floor[CityRoad[b]];  //两个层之间有相通的城市,因而可以归为一个层
                            }
                        }

                        MinAdd--;
                    }

                    else if
(floor[CityRoad[a]] < floor[CityRoad[b]])
                    {

                        temp = floor[CityRoad[b]];   
                        for
(j = 1; j < part + 1; j ++)
                        {

                            if
(floor[j] == temp)
                            {

                                floor[j] =  floor[CityRoad[a]];  //两个层之间有相通的城市,因而可以归为一个层
                            }
                        }

                        MinAdd--;
                    }
                }
            }
        }

        printf("%d/n",MinAdd);
    }
}

这是我一朋友AC过的并查集代码 比较简洁,高效。

#include <stdio.h>
#define NUM 1000
int pre[NUM];

void
reset()
{

    for
(int i=0;i<NUM;i++)
        pre[i] = i;
}


int
find_pre(int i)
{

    if
(pre[i]!=i)
        pre[i] = find_pre(pre[i]);
    return
pre[i];
}


int
append(int a, int b)
{

    int
pre_a, pre_b;
    pre_a = find_pre(a);
    pre_b = find_pre(b);
    if
(pre_a == pre_b) return 0;
    pre[pre_a] = pre_b;
    return
1;
}


int
main()
{

    int
N,M,ans,a,b,i;
    while
(scanf("%d",&N),N)
    {

        scanf("%d",&M);
        reset();
        ans = N-1;
        for
(i=0;i<M;i++)
        {

            scanf("%d%d",&a,&b);
            if
(append(a,b)) ans--;
        }

        printf("%d/n",ans);
    }
}


分享给朋友:
您可能感兴趣的文章:
随机阅读: