• ACM-最小生成树之继续畅通project——hdu1879


    版权声明:本文为博主原创文章,未经博主同意不得转载。 https://blog.csdn.net/lx417147512/article/details/27092583

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


    继续畅通project

    Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
    Total Submission(s): 12918    Accepted Submission(s): 5587


    Problem Description
    省政府“畅通project”的目标是使全省不论什么两个村庄间都能够实现公路交通(但不一定有直接的公路相连,仅仅要能间接通过公路可达就可以)。现得到城镇道路统计表,表中列出了随意两城镇间修建道路的费用,以及该道路是否已经修通的状态。现请你编敲代码,计算出全省畅通须要的最低成本。
     

    Input
    測试输入包括若干測试用例。每一个測试用例的第1行给出村庄数目N ( 1< N < 100 );随后的 N(N-1)/2 行相应村庄间道路的成本及修建状态,每行给4个正整数。各自是两个村庄的编号(从1编号到N)。此两村庄间道路的成本。以及修建状态:1表示已建,0表示未建。

    当N为0时输入结束。

     

    Output
    每一个測试用例的输出占一行,输出全省畅通须要的最低成本。
     

    Sample Input
    3 1 2 1 0 1 3 2 0 2 3 4 0 3 1 2 1 0 1 3 2 0 2 3 4 1 3 1 2 1 0 1 3 2 1 2 3 4 1 0
     

    Sample Output
    3 1 0
     

    Author
    ZJU
     

    Source
     

    题目:http://acm.hdu.edu.cn/showproblem.php?pid=1879


    继续畅通project,最小生成树(MST)。

    不说最小生成树,直接说MST,是不是显得高大上啊~
    嘿嘿~~~

    这道题,依然是求最小生成树。比起赤裸裸加了几块布。
    比方,有些路已经修建了。
    已经修建的路就不须要耗费你不论什么东西,所以cost=0
    没有告诉你边数有多少。
    事实上题目中说了 边数=n*(n-1)/2

    剩下的,求MST吧~ 。我用的Kruskal求:

    /****************************************
    *****************************************
    *        Author:Tree                    *
    *From :http://blog.csdn.net/lttree      *
    * Title : 继续畅通project                 *
    *Source: hdu 1879                       *
    * Hint  : 最小生成树(MST-Prim)       *
    *****************************************
    ****************************************/
    
    #include <stdio.h>
    #include <algorithm>
    using namespace std;
    struct Road
    {
        int u,v,c;
    }r[10001];
    int n,m,father[10001];
    bool cmp(Road r1,Road r2)
    {
        return r1.c<r2.c;
    }
    
    // 并查集系列函数  1-初始化 2-查找 3-合并
    void Init( int n )
    {
        int i;
        for(i=1;i<=n;++i)
            father[i]=i;
    }
    int Find(int m)
    {
        while( father[m]!=m )
        {   m=father[m];    }
        return m;
    }
    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;
    }
    
    int Kruskal( void )
    {
        sort(r,r+m,cmp);
        Init(n);
        Road rd;
        int i,res;
    
        // 构建最小生成树
        res=0;
        for( i=0;i<m;++i )
        {
            rd=r[i];
            if( Find(rd.u)!=Find(rd.v) )
            {
                Combine(rd.u,rd.v);
                res+=rd.c;
            }
        }
        return res;
    }
    
    int main()
    {
        int i,start,finish,cost,iscon;
    
        while( scanf("%d",&n) && n )
        {
            // 求边的数量
            m = n*(n-1)/2;
            for( i=0;i<m;++i )
            {
                scanf("%d%d%d%d",&start,&finish,&cost,&iscon);
                r[i].u=start;
                r[i].v=finish;
                // 假设道路已经修建。消耗设置为0,不须要我们再去建立道路
                if( iscon ) r[i].c=0;
                else    r[i].c=cost;
            }
            printf("%d
    ",Kruskal());
        }
        return 0;
    }
    


  • 相关阅读:
    Java中的引用
    JVM参数调优
    GCRoots
    JVM体系结构
    死锁编码及定位分析
    线程池(Java中有哪些方法获取多线程)
    Synchronized和Lock的区别
    阻塞队列BlockingQueue
    CountDownLatch/CyclicBarrier/Semaphore
    浅谈二分
  • 原文地址:https://www.cnblogs.com/ldxsuanfa/p/10576603.html
  • 一二三 - 开发者的网上家园