ACM-光滑最小生成树project——hdu1863

2022-11-10 18:37:11

转载请注明出处：http://blog.csdn.net/lttree

畅通project

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 15572 Accepted Submission(s): 6462

Problem Description

省*“畅通project”的目标是使全省不论什么两个村庄间都能够实现公路交通（但不一定有直接的公路相连。仅仅要能间接通过公路可达就可以）。经过调查评估。得到的统计表中列出了有可能建设公路的若干条道路的成本。

现请你编敲代码，计算出全省畅通须要的最低成本。

Input

測试输入包括若干測试用例。每一个測试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 )；随后的 N

行相应村庄间道路的成本。每行给出一对正整数，各自是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。

为简单起见，村庄从1到M编号。当N为0时，所有输入结束，相应的结果不要输出。

Output

对每一个測试用例。在1行里输出全省畅通须要的最低成本。若统计数据不足以保证畅通，则输出“?”。

Sample Input

Sample Output

3

?

Source

浙大计算机研究生复试上机考试-2007年

题目：

pid=1863">http://acm.hdu.edu.cn/showproblem.php?pid=1863

最小生成树的基础题目。畅通project。

赤裸裸的求最小生成树。

额外加了一点要推断能否构成最小生成树。

这次，我用的Kruskal算法。

Kruskal 构建最小生成树：

大体。就是先依照边长进行排序（由小到大），

然后再向外加边。

加边的时候推断是否能构成回路，假设能构成回路，就不能加边。

为什么这么做是对的呢？

首先。要知道，最小生成树，一定不会出现回路！

Why？自己算算。。

o(╯□╰)o。

。

然后，我们已经将边依照小到大排序了，所以这样加边，得到的肯定是最小生成树啦~

Kruskal算法重要的就是推断回路。

这个是用并查集来实现的，（并查集相关可戳：http://blog.csdn.net/lttree/article/details/23820679）

然后。最后再用并查集Find函数来找找。是否全部的点都在同一个集合，假设不在，输出？

恩，OK~

/****************************************

*****************************************

*        Author:Tree                    *

*From :http://blog.csdn.net/lttree      *

* Title : 畅通project                     *

*Source: hdu 1863                       *

* Hint  : 最小生成树（Kruskal）        *

*****************************************

****************************************/

#include <stdio.h>

#include <algorithm>

using namespace std;

struct EDGE

{

    int u,v,cost;

}eg[100001];

int n,m,father[100001];

bool cmp(EDGE e1,EDGE e2)

{

    return e1.cost<e2.cost;

}

// 并查集 初始化函数

void Init( int m )

{

    int i;

    for(i=1;i<=m;i++)

        father[i]=i;

}

// 并查集 查找函数

int Find(int x)

{

    while(father[x]!=x)

        x=father[x];

    return x;

}

// 并查集 合并函数

void Combine(int a,int b)

{

    int temp_a,temp_b;

    temp_a=Find(a);

    temp_b=Find(b);

    if(temp_a!=temp_b)

        father[temp_a]=temp_b;

}

// 最小生成树 Kruskal 算法

int Kruskal( void )

{

    EDGE e;

    int i,res;

    sort(eg,eg+n,cmp);

    // 并查集 初始化

    Init(m);

    // 构建最小生成树

    res=0;

    for( i=0;i<n;++i )

    {

        e=eg[i];

        if( Find(e.u)!=Find(e.v) )

        {

            Combine(e.u,e.v);

            res+=e.cost;

        }

    }

    return res;

}

int main()

{

    int i,ans;

    bool bl;

    while( scanf("%d%d",&n,&m) && n )

    {

        for( i=0;i<n;++i )

            scanf("%d%d%d",&eg[i].u,&eg[i].v,&eg[i].cost);

        ans=Kruskal();

        // 是否全部的点都在同一个集合

        bl=true;

        for(i=2;i<=m;++i)

            if( Find(1)!=Find(i) )

            {

                bl=false;

                break;

            }

        if( bl )    printf("%d\n",ans);

        else    printf("?\n");

    }

    return 0;

}

又搞了搞最小生成树的Prim算法。

。。

Prim算法就是从一个点慢慢扩展到全图。

原理：

就是从一个点出发，然后从全部与这个点直接相连的点中。找权值最小的那条边。进行扩展。

可是。不用每次都寻找，仅仅须要在增加一个点后，

更新这个集合到其它各个点的距离，就可以。

Prim和Kruskal差别：

我的理解是：

Prim是一个集合战斗，慢慢扩展，一个个吞并，最后构成一个大树。

而Kruskal 是多个集合（≥1，也可能是一个集合）分别作战，最后合并成一个大树。

Prim和Kruskal优劣性：

Prim须要每次都维护mincost数组（距离各个点的最短距离），所以须要O（n^2）

可是同最短路的Dijkstra一样，假设用堆来维护，则复杂度可降到 O（n log n）

Kruskal算法仅仅是在排序上最费时，算法复杂度可看做 O（ n log n ）

本题的Prim算法：

/****************************************

*****************************************

*        Author:Tree                    *

*From :http://blog.csdn.net/lttree      *

* Title : 畅通project                     *

*Source: hdu 1863                       *

* Hint  : 最小生成树（Prim   ）        *

*****************************************

****************************************/

#include <stdio.h>

#include <string.h>

#define RANGE 101

#define MAX 0x7fffffff

int cost[RANGE][RANGE];

int mincost[RANGE];

bool used[RANGE];

// n个点。m条边

int n,m;

int Min(int a,int b)

{

    return a<b?a:b;

}

void prim( void )

{

    // sum 记录最小生成树权值

    int i,v,u,sum;

    // 从1到各个点距离，初始化used数组

    for( i=1;i<=n;++i )

    {

        used[i]=false;

        mincost[i]=cost[1][i];

    }

    sum=0;

    while( true )

    {

        v=-1;

        // 从没有连接到的点中，找近期的点

        for( u=1;u<=n;++u )

            if( !used[u] && (v==-1 || mincost[u]<mincost[v]) )

                v=u;

        if( v==-1 ) break;

        if( mincost[v]==MAX )   break;

        used[v]=true;

        sum+=mincost[v];

        // 更新到各个点的距离

        for( u=1;u<=n;++u )

            mincost[u]=Min( mincost[u],cost[v][u] );

    }

    // 推断是否能构成最小生成树

    for( i=1;i<=n;++i )

    {

        if( used[i]==false )

        {

            printf("?\n");

            return;

        }

    }

    printf("%d\n",sum);

}

int main()

{

    int i,j;

    int u,v,c;

    while( scanf("%d%d",&m,&n) && m )

    {

        // init cost by MAX

        for( i=1;i<=n;++i )

            for( j=1;j<=i;++j )

            {

                if( i==j )  cost[i][j]=0;

                else    cost[i][j]=cost[j][i]=MAX;

            }

        for( i=0;i<m;++i )

        {

            scanf("%d%d%d",&u,&v,&c);

            cost[u][v]=cost[v][u]=c;

        }

        prim();

    }

    return 0;

}

码农公寓

***************************************转载请注明出处：http://blog.csdn.net/lttree***************************************

畅通project

相关文章

转载请注明出处：http://blog.csdn.net/lttree