`
128kj
  • 浏览: 601667 次
  • 来自: ...
社区版块
存档分类
最新评论

POJ 1679 练习克鲁斯卡尔kruskal 算法

阅读更多
克鲁斯卡尔kruskal 算法 
   假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网,则按照克鲁斯卡尔算法构造最小生成树的过程为:
   先构造一个只含 n 个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点,则它是一个含有 n 棵树的一个森林。之后,从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,也就是说,将这两个顶点分别所在的两棵树合成一棵树;反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直至子图中含有 n-1条边为止。

POJ1679:The Unique MST

题意:给一个无向图,判断这个图的最小生成树MST是否是唯一的。如果是唯一的,输出最小生成树的权值,如果不是唯一的,输出“Not Unique!” 

分析:先求出一棵最小生成树,记下最小权值为mst.然后枚举树上的每条边,去掉以后再求一次最小生成树,只要出现权值等于mst,那么最小生成树一定不唯一.


样例:
Sample Input

2(测试次数)
3 3(顶点和边的数目)
1 2 1(一条边的两个顶点和权值,以下同)
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2

Sample Output

3
Not Unique!


AC代码:
import java.util.Scanner;      
import java.util.Arrays;      
public class Main{      
    private int father[];    //记录顶点的父节点  
    private Edge e[];   //图的所有边   
    private int n;//结点个数      
    private int l;//边的数目 
    private int mst;//最小生成树的最小权值
    private boolean uni;//最小生成树是否唯一的标志

    public Main(int n,int l,Edge[] e){      
       this.n=n;      
       this.l=l;      
       this.e=e;      
       father=new int[n+1];  
       mst=0;
       uni=true;    
       make_set();     
          
             
    }         

   private void make_set(){//将每个顶点初始化为一个集合(树),父节点指向自己。 
     for( int x = 1; x <= n; x ++)
        father[x] = x;
   }


   private int find_set(int x){//找x的父节点
    if(x != father[x])
        father[x] = find_set(father[x]);//路径压缩
    return father[x];
    }

    public int getMst(){
      return this.mst;
    }

    public boolean getUni(){
      return this.uni;
    }

  private void kruskal(){
    int  x, y;
    int mst_e[]=new int[n];//用于记录第一次krushal得到的MST的边
    int edge_num=0;//第一次krushal后的边数;
    int k = 0;
      // 下面为第一次kruskal求MST。
    make_set();    
    Arrays.sort(e);//将边按权值排序(从小到大)
     for(int i = 0; i < l; i ++){
        x = find_set(e[i].a);
        y = find_set(e[i].b);
        if(x != y){
            father[y] = x;//合并两棵树
            mst += e[i].weight;
            mst_e[k ++] = i;   //  记录下MST的边。
        }
    }
    edge_num = k;//  记录MST的边的数目
   
   
    for(int r = 0; r < edge_num; r ++){//枚举树上的每条边,去掉以后再求一次最小生成树,
         make_set();     //  每次kruskal要记得初始化并查集。
         int sec_mst=0;//用于记录下面求出的最小生成树的最小权值
         int num = 0;
        for(int i = 0; i < l; i ++){
            if(i == mst_e[r]) continue;   //  模拟删边。
            x = find_set(e[i].a);
            y = find_set(e[i].b);
            if(x != y){
                father[y] = x;
                sec_mst += e[i].weight;
                num ++;
            }
        }
        if(num != edge_num) continue;   //判断是能构成完整的次小生成树。
        if(sec_mst == mst){
         //System.out.println(mst);
  //如果能构造成完整的次小生成树,并且次小生成树的值与mst相等,则说明MST不唯一。
            uni = false;
            return;
        }
    } 
}

 

 public static void main(String args[]){
    Scanner in=new Scanner(System.in);
    int t=in.nextInt();
    
    while(t -->0){
        int n=in.nextInt();//顶点数
        int m=in.nextInt();//边数
        Edge[] e=new Edge[m];   
      for(int i = 0; i <m; i++){   
          e[i]=new Edge(in.nextInt(),in.nextInt(),in.nextInt());   
             
      }   
      Main ma=new Main(n,m,e);   
     
      ma.kruskal();
        if(!ma.getUni()) System.out.printf("Not Unique!\n");
        else System.out.printf("%d\n", ma.getMst());
    }
  }
  
}


class Edge implements Comparable       
     
{        
     int a;  //边的一个顶点,从数字0开始      
     int b;  //边的另一个顶点      
     int weight;  //权重      
     
     Edge(int a,int b,int weight){      
      this.a=a;      
      this.b=b;      
      this.weight=weight;      
    }      
     
    @Override         
    public int compareTo(Object o){       
        Edge m = (Edge)o;       
        int result=(int)(this.weight - m.weight);       
        if(result>0) return 1;      
        else if(result==0) return 0;      
        else return -1;      
    }       
     
}    
0
2
分享到:
评论

相关推荐

    次小生成树(POJ 1679 The Unique MST)

    先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...

    POJ算法题目分类

    * 最小生成树算法:最小生成树算法是指计算图的最小生成树的算法,如 prim、kruskal。 * 拓扑排序:拓扑排序是指计算图的拓扑排序的算法,如 poj1094。 * 二分图的最大匹配:二分图的最大匹配是指计算二分图的最大...

    POJ练习题算法分类

    根据提供的文件信息,我们可以将POJ练习题中的算法进行分类,并对每一类中的知识点进行详细的阐述。POJ(Pacific Ocean Judge)是一个在线编程平台,它提供了丰富的编程题目,旨在帮助学习者掌握各种基础算法和数据...

    北大POJ初级-基本算法

    【北大POJ初级-基本算法】是一系列针对北京大学在线编程平台POJ的初级算法题目解题报告和通过(AC)代码的集合。这个资源对于学习算法基础和提升编程能力非常有帮助,尤其适合初学者。POJ是许多计算机科学与技术专业...

    北大POJ初级-图算法

    【北大POJ初级-图算法】是一系列针对北京大学在线编程平台POJ(Problem Online Judge)上的初级编程题目,重点在于图论算法的应用。这个解题报告集合了多种图算法的实现,帮助学习者掌握如何在实际问题中运用这些...

    poj acm 题解 算法

    POJ是中国北京大学维护的一个在线编程练习系统,提供了大量的编程题目供参赛者练习。 【描述】提到的"poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究"表明这份压缩包内包含的是对POJ平台上...

    POJ中级图算法所有题目【解题报告+AC代码】

    在编程竞赛领域,POJ(Programming Online Judge)是一个广受欢迎的在线编程平台,它提供了许多题目供参赛者解决,以提升编程和算法能力。本文主要关注的是“POJ中级图算法”的一系列题目及其解题报告和AC(Accepted...

    poj 2485 Highways 测试数据

    【poj 2485 Highways 测试数据】是一个编程竞赛题目,源自著名的在线算法竞赛平台POJ(Programming Online Judge)。此题目的主要目的是通过解决实际问题来考察参赛者的图论和算法设计能力,特别是涉及到最小生成树...

    POJ第1861题源码POJ第1861题源码POJ第1861题源码POJ第1861题源码

    对于POJ第1861题,参赛者可能需要读取输入数据,构建一个加权图,然后应用Prim或Kruskal算法找出最小生成树,最后输出树中边的权重总和或者某种特定格式的树结构。解题过程可能涉及到错误处理、边界条件检查以及效率...

    poj算法题目实现.zip_algorithm_arrangement4hv_conditionyis_poj problems

    在本压缩包“poj算法题目实现.zip”中,包含了五个经典的编程竞赛题目,主要针对的是POJ(Programming Online Judge)平台。这些题目是程序员提升算法能力、锻炼编程技巧的重要资源。下面,我们将详细探讨每个题目...

    poj题目分类

    * 最小生成树算法:例如 Prim、Kruskal,例如 poj1789、poj2485、poj1258、poj3026。 * 拓扑排序:例如 poj1094。 * 二分图的最大匹配:例如 poj3041、poj3020。 * 最大流的增广路算法:例如 poj1459、poj3436。...

    ACM常用算法及其相应的练习题.docx

    ACM常用算法及其相应的练习题 本资源总结了 ACM 竞赛中常用的算法和相应的练习题,涵盖了基础算法、图算法、数据结构、搜索、动态规划和数学等方面的知识点。 一、基础算法 * 枚举:poj1753, poj2965 * 贪心:poj...

    POJ 1751 求最小生成树prim算法(JAVA)

    标题 "POJ 1751 求最小生成树Prim算法(JAVA)" 提到的是一个编程挑战,涉及图论中的经典算法——Prim算法。在计算机科学中,Prim算法是用于寻找加权无向图的最小生成树的一种有效方法。最小生成树是一棵树形结构,...

    poj训练计划.doc

    - 最小生成树算法:如Prim算法和Kruskal算法,用于找出图中的最小生成树,如`poj1789, poj2485`。 - 拓扑排序:适用于有向无环图,用于确定任务的执行顺序,如`poj1094`。 - 二分图的最大匹配:如匈牙利算法,...

    acm训练计划(poj的题)

    - (poj1789, poj2485, poj1258, poj3026):介绍普里姆算法(Prim)和克鲁斯卡尔算法(Kruskal),用于寻找加权无向图的最小生成树。 4. **拓扑排序**: - (poj1094):适用于有向无环图(DAG)的一种排序方式,...

    ACM-POJ 算法训练指南

    2. **最小生成树**:Prim算法和Kruskal算法,用于构建图的最小生成树(poj1789, poj2485, poj1258, poj3026)。 3. **网络流**:Max-flow算法,用于解决最大流问题(poj1094)。 4. **拓扑排序**:解决有向无环图的...

    POJ 1077 算法

    标题中的“POJ 1078 算法”指的是北京大学在线判题系统(Problem Online Judge,简称POJ)中的第1077题,这通常是一个编程竞赛或者算法练习题目。POJ是一个供程序员练习算法、提交代码并获取运行结果的平台,主要...

    POJ3308-Paratroopers 【Dinic算法求最大流】

    【二分图顶点覆盖-&gt;最小割-&gt;最大流-&gt;Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----&gt; 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573

    POJ各题算法分类和题目推荐 ACM必看

    POJ算法分类和题目推荐指南 本资源主要介绍了POJ(Online Judge)平台上各种算法分类和推荐题目,涵盖了动态规划、模拟、博弈等多种类型。以下是详细的知识点说明: 一、动态规划 动态规划是一种非常重要的算法...

Global site tag (gtag.js) - Google Analytics