修复公路

修复公路

全栈程序员-站长 • 2026年3月19日上午11:57 • 未分类 • 阅读 3

题目链接：https://www.luogu.org/problemnew/show/P1111

显而易见，这道题目使用的是并查集与生成树，查询x村庄和y村庄时候相连

-1的情况也很好判断（我用了一种很自己认为弱智的算法进行判断）

还有一个问题，怎样求出最小的各点全连通的时间？

可以考虑以下思路：将各个道路按照建造的时间排序，每次combine两个村庄的时候就可以更新当前的时间，当前时间即为“最早各点连通时间”【因为两点连通过后下次的判断可以直接跳过，不考虑建造这条道路，由此可知此算法正确】

以下是代码：

 1 #include 
    
     2 #include 
     
      3 #include 
      
       4 #include 
       
        5 #include 
        
         6 
        using 
        namespace 
         std;  
         7 
        const 
        int N= 
        1005 
        ;  
         8 
        int 
         t[N][N],father[N];  
         9 
        int find( 
        int 
         x)  
        10 
        {  
        11 
        if(father[x]!= 
        x)  
        12 father[x]= 
        find(father[x]);  
        13 
        return 
         father[x];  
        14 
        }  
        15 
        void combine( 
        int x, 
        int 
         y)  
        16 
        {  
        17 
        int 
         t1,t2;  
        18 t1= 
        find(x);  
        19 t2= 
        find(y);  
        20 
        if(t1!= 
        t2)  
        21 father[t1]= 
        t2;  
        22 
        }  
        23 
        struct 
         build  
        24 
        {  
        25 
        int 
         tm,x,y;  
        26 }a[ 
         
        ];  
        27 
        bool 
         cmp(build p,build q)  
        28 
        {  
        29 
        return p.tm< 
        q.tm;  
        30 
        }  
        31 
        int 
         n,m;  
        32 
        int 
         main()  
        33 
        {  
        34 
        int 
         x,y,tm,minn;  
        35 cin>>n>> 
        m;  
        36 
        for( 
        int i= 
        1;i<=n;++ 
        i)  
        37 father[i]= 
        i;  
        38 
        for( 
        int i= 
        1;i<=m;++ 
        i)  
        39 cin>>a[i].x>>a[i].y>> 
        a[i].tm;  
        40 sort(a+ 
        1,a+m+ 
        1 
        ,cmp);  
        41 
        for( 
        int i= 
        1;i<=m;++ 
        i)  
        42 
         {  
        43 
        if(find(a[i].x)!= 
        find(a[i].y))  
        44 
         {  
        45 minn= 
        a[i].tm;  
        46 
         combine(a[i].x,a[i].y);  
        47 
         }  
        48 
         }  
        49 
        for( 
        int i= 
        2;i<=n;++ 
        i)  
        50 
         {  
        51 
        if(find( 
        1)!= 
        find(i))  
        52 
         {  
        53 cout<< 
        " 
        -1 
        "<< 
        endl;  
        54 
        return 
        0 
        ;  
        55 
         }  
        56 
         }  
        57 cout< 
        
          endl; 
         58 
         return 
         0 
         ;  
         59 }

总结：遇到此类（如同连通块、并查集等）求各点全连通的题目，可以考虑对时间（价值）进行排序以求出最小时间。

转载于:https://www.cnblogs.com/cptbtptpbcptbtptp/p/11140547.html

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/208279.html原文链接：https://javaforall.net

关于作者

全栈程序员-站长

发表回复

修复公路

关于作者

全栈程序员-站长

相关推荐

【SQL Server】网上购物商城数据库设计报告(专业课设作品附上sql文件文档)

python 函数def

linux抓包命令tcpdump保存到wireshark_tcpdump抓包命令举例

微信小程序 40029错误

Excel设置(单行或多行)固定表头的方法

3分钟教你用DeepSeek+即梦做出AI跨时空对话，太火爆了！

发表回复