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

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
分享到:
评论

相关推荐

    acm训练计划(poj的题)

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

    ACM 新手指南 PKU 题目分类

    - **最小生成树**:主要算法有普里姆算法(Prim)和克鲁斯卡尔算法(Kruskal),用于求解无向图中的最小生成树。 - 示例题目:POJ 1789, POJ 2485, POJ 1258, POJ 3026 - **网络流**:涉及到最大流、最小割等问题,...

    北大ACM 题目分类

    - 最小生成树算法:了解普里姆算法和克鲁斯卡尔算法的工作原理及其适用条件。 - 其他图论知识,如网络流、二分图匹配(`KM算法`)等。 #### 5. 数据结构 - **题目**: 包括字符串处理(`hash`)、树状数组(`poj3253`)...

    边缘计算中资源卸载与群智能优化算法的应用及定制

    内容概要:本文探讨了边缘计算环境中资源卸载的关键技术和群智能优化算法的应用。首先介绍了边缘计算资源卸载的基本概念及其重要性,展示了通过Python代码实现资源卸载的具体方法。接着详细讨论了群智能优化算法(如粒子群算法)在资源卸载中的应用,解释了如何通过调整适应度函数来优化卸载决策。最后,文章深入探讨了针对特定应用场景对群智能算法进行定制的方法,强调了在实际部署中需要考虑的因素,如计算能力、带宽限制和能量消耗等。 适合人群:对边缘计算和群智能优化算法感兴趣的科研人员、工程师和技术爱好者。 使用场景及目标:适用于研究和开发边缘计算系统的企业和个人,旨在提高资源利用效率,降低延迟和能耗,优化任务分配。 其他说明:文中提供的代码示例有助于理解和实践相关理论,同时也指出了现有算法存在的局限性和改进方向。

    基于西门子S7-200 PLC与组态王的矿井提升机控制系统设计及应用

    内容概要:本文详细介绍了利用西门子S7-200 PLC和组态王构建矿井提升机控制系统的全过程。首先阐述了硬件配置选择,包括选用S7-224XP型号及其扩展模块,确保速度反馈和变频器调速等功能。接着深入探讨了PLC程序设计的关键部分,如速度闭环控制、PID参数调整、安全回路设计以及通信协议的应用。同时,文中展示了组态王用于监控和报警的具体实现方法,强调了可视化动画和历史曲线的功能。此外,作者分享了多个调试过程中遇到的问题及解决方案,如抗电磁干扰措施、抱闸时序优化等。最后总结了该系统在实际应用中的稳定表现,显著降低了故障率。 适合人群:从事工业自动化领域的工程师和技术人员,尤其是对PLC编程和组态软件有一定基础的从业者。 使用场景及目标:适用于需要设计和实施矿井提升机或其他类似复杂机械设备控制系统的场合。目标是提高系统的安全性、可靠性和效率,减少故障发生频率。 其他说明:文中提供了大量实用的技术细节和实践经验,对于理解和掌握PLC编程技巧、解决实际工程问题具有重要参考价值。

    储能系统参与调峰调频联合调度的Matlab建模与优化

    内容概要:本文详细探讨了储能系统在电力系统中同时参与调峰和调频的联合调度模型及其Matlab实现。文中指出,传统的调峰和调频模型通常是分离的,而将两者结合起来能够显著提高储能系统的经济效益。文章介绍了如何构建一个考虑电池退化成本、充放电功率约束以及用户负荷不确定性的储能优化模型,并提供了具体的Matlab代码示例。此外,还讨论了模型中的关键技术和实现细节,如充放电互斥约束、电池损耗计算、负荷不确定性处理等。 适合人群:从事电力系统优化、储能技术研发及相关领域的研究人员和技术人员。 使用场景及目标:适用于希望深入了解储能系统在电力系统中如何通过联合调度实现经济利益最大化的专业人士。目标是掌握储能系统在调峰调频方面的优化方法和技术手段。 其他说明:文中提到的模型和代码对于理解和解决储能系统在实际应用中的挑战具有重要指导意义。特别是针对负荷预测误差、电池老化等问题提出了有效的解决方案。

    基于Matlab/Simulink的ACDCAC变频移相技术电力电子仿真与模型实践

    内容概要:本文详细介绍了如何利用Matlab/Simulink进行ACDCAC变频移相系统的仿真建模。首先,作者讲解了创建基本模型的步骤,包括选择合适的PWM变流器、设置LC滤波器参数以及配置IGBT开关频率。接着,深入探讨了移相控制的核心技术,如调制波生成、相位差设置、PI控制器参数整定等。此外,文中还提供了许多实用的小技巧,如优化仿真步长、避免波形失真、处理IGBT损耗等问题。最后,强调了仿真过程中需要注意的关键点,如正确设置接地、选择合适的求解器等。 适合人群:从事电力电子研究的技术人员、高校相关专业师生、对电力电子仿真感兴趣的工程爱好者。 使用场景及目标:适用于希望深入了解ACDCAC变频移相系统工作原理及其仿真的读者;帮助读者掌握使用Matlab/Simulink构建复杂电力电子系统的方法;提供实际操作指导,使读者能够独立完成类似项目的仿真。 其他说明:文中不仅涵盖了理论知识,还包括大量实战经验和代码片段,有助于提高读者的实际动手能力。同时,作者分享了许多个人经验教训,使得文章更具实用性。

    DC-DC隔离电源芯片BB的应用与优化:5V输入输出、400kHz开关频率的高效解决方案

    内容概要:本文详细介绍了BB公司生产的DC-DC隔离电源芯片的应用及其优化方法。该芯片输入电压范围为5V~5.5V,输出电压5V,最大输出电流200mA,开关频率高达400kHz。文章首先探讨了芯片的基本参数和应用场景,特别是针对数字电路和模拟电路共存时的干扰问题。接着,作者分享了具体的电路设计经验,如反馈电阻的选择、SW引脚波形的优化以及PCB布局技巧。此外,文中还讨论了双芯片并联使用的负载均衡算法,并提供了STM32配置软启动功能的具体代码。最后,强调了电源隔离对于减少地环路干扰的重要性,并给出了多个实际案例和技术细节。 适合人群:从事电力电子、嵌入式系统开发的技术人员,尤其是对DC-DC隔离电源设计感兴趣的工程师。 使用场景及目标:①解决数字电路与模拟电路共存时的干扰问题;②提高电源系统的稳定性和效率;③掌握高频开关电源的设计和优化技巧。 其他说明:文章不仅提供了理论分析,还有大量实践经验分享,包括具体参数选择、电路设计、PCB布局等方面的注意事项。

    ABAQUS中复合式密封垫的动力显示分析步建模与后处理分析

    内容概要:本文详细介绍了如何在ABAQUS中进行复合式密封垫的动力显示分析步建模及其后处理分析。主要内容涵盖材料参数设置、建模技巧、接触对设置、时间增量控制以及后处理提取接触应力的方法。文中强调了使用Mooney-Rivlin模型定义EPDM和WSR材料参数的重要性,并提供了具体的.inp文件和Python脚本示例。同时,讨论了膨胀率设置、接触算法选择、质量缩放参数的应用以及膨胀过程中应力分布的特点。 适合人群:从事有限元分析、密封件设计及相关领域的工程师和技术人员。 使用场景及目标:适用于需要精确模拟复合式密封垫在复杂工况下(如遇水膨胀)的行为的研究项目。主要目标是帮助用户掌握ABAQUS中动力显示分析步的具体应用,提高仿真精度和效率。 其他说明:文章不仅提供了详细的理论解释,还附带了大量的代码片段和实践经验,有助于读者更好地理解和应用所学知识。此外,文章还探讨了一些常见的陷阱和解决方案,如膨胀参数设置不当、接触定义不合理等问题。

    页岩气开采中二氧化碳驱替甲烷的COMSOL多物理场仿真及优化

    内容概要:本文详细介绍了利用COMSOL进行二氧化碳驱替甲烷的多物理场仿真过程。首先构建了二维多物理场模型,选择达西定律和稀物质传递作为主要物理场,重点考虑了孔隙结构、材料参数(如黏度、渗透率)、边界条件(如注气井的压力和质量流量)以及求解器设置。文中强调了网格划分、参数设置、边界条件和求解器配置的具体操作和技术要点,展示了如何通过数值模拟研究二氧化碳驱替甲烷过程中可能出现的现象,如粘性指进、浓度场演化等。此外,还探讨了不同注入速度和压力对驱替效果的影响,提出了参数敏感性分析的重要性。 适合人群:从事页岩气开采、二氧化碳封存及相关领域的科研人员、工程师和技术爱好者。 使用场景及目标:适用于希望深入了解二氧化碳驱替甲烷机理的研究人员,以及希望通过数值模拟优化实际工程设计的工程师。目标是提高甲烷采收率并实现有效的碳封存。 其他说明:文中提供了详细的建模步骤和代码片段,帮助读者更好地理解和应用COMSOL进行相关仿真。同时提醒读者关注参数敏感性和实际地层条件的匹配,确保模拟结果的准确性。

    tesseract-langpack-nor-4.0.0-6.el8.x64-86.rpm.tar.gz

    1、文件说明: Centos8操作系统tesseract-langpack-nor-4.0.0-6.el8.rpm以及相关依赖,全打包为一个tar.gz压缩包 2、安装指令: #Step1、解压 tar -zxvf tesseract-langpack-nor-4.0.0-6.el8.tar.gz #Step2、进入解压后的目录,执行安装 sudo rpm -ivh *.rpm

    MATLAB中基于CNN-BIGRU的时序数据分析与分类模型实现及优化

    内容概要:本文详细介绍了如何在MATLAB中利用卷积神经网络(CNN)和双向门控循环单元(BIGRU)进行时序数据的分类任务。首先阐述了模型的基本结构,包括卷积层用于提取局部特征,以及BIGRU层用于捕捉时序依赖。接着讨论了数据预处理方法,如数据归一化、滑窗处理和数据集划分。然后探讨了训练配置的关键参数选择,如优化器、学习率调度器和批量大小等。此外,还强调了模型评估的重要性,提出了除了准确率外还需关注混淆矩阵、AUC等指标。最后分享了一些实际应用中的经验和技巧,例如将模型转化为ONNX格式以提高推理效率。 适合人群:具有一定MATLAB编程基础和技术背景的研究人员、工程师或学生。 使用场景及目标:适用于需要处理时序数据并进行分类的任务,如医疗诊断、金融预测、工业设备状态监测等。目标是帮助读者掌握CNN-BIGRU模型的设计、实现及其优化方法。 其他说明:文中提供了大量实用的代码片段和实践经验,有助于读者更好地理解和应用所介绍的技术。

    Day06【使用Word2Vec模型训练词向量】-词向量训练

    用于词向量训练等语料文件

    基于51单片机protues仿真的酒驾报警系统控制(仿真图、源代码、AD原理图、流程图)

    基于51单片机protues仿真的酒驾报警系统控制(仿真图、源代码、AD原理图、流程图) 酒驾报警: 1、通过AD芯片和传感器检测酒精浓度; 2、设置不同的报警值,喝酒检测和醉酒状态检测,LED指示不同的报警状态; 3、检测到喝酒状态,报警;检测到醉酒状态,启动刹车; 4、液晶屏显示相关信息; 5、仿真图、源代码、AD原理图、流程图;

    web开发项目前端页面搭建

    web开发项目前端页面搭建

    二阶线性自抗扰控制模型的Python实现及其在工程领域的应用

    内容概要:本文介绍了二阶线性自抗扰控制(LADRC)模型的原理与Python实现。自抗扰控制是一种先进的控制策略,适用于处理系统中的不确定性和外部干扰。文中详细解释了LADRC的三大组成部分:跟踪微分器(TD)、扩张状态观测器(ESO)和非线性状态误差反馈控制律(NLSEF)。此外,提供了具体的Python代码示例,展示了如何构建并使用LADRC进行实际控制任务,如电机转速控制和四旋翼飞行器控制。文章还讨论了关键参数的选择和调试技巧,强调了ESO在实时估计系统状态和扰动方面的重要作用。 适合人群:具有一定编程基础和控制理论知识的研发人员和技术爱好者。 使用场景及目标:①需要提高控制系统鲁棒性的工程项目;②希望减少对外部干扰敏感度的应用场合;③寻求替代传统PID控制器的高效解决方案。 其他说明:文中提供的代码可以直接应用于实际项目中,只需根据具体应用场景调整相关参数即可获得良好的控制性能。同时,附带了一些实用的调试建议,有助于解决常见的实施难题。

    华为云2024知行合一通信行业数据治理实践指南53页.pdf

    华为云2024知行合一通信行业数据治理实践指南53页.pdf

    MATLAB实现电-气-热综合能源系统耦合优化调度模型

    内容概要:本文详细介绍了基于MATLAB的电-气-热综合能源系统耦合优化调度模型。该模型旨在通过优化电网、气网和热网之间的协同运作,提高能源利用效率。文中具体展示了如何构建和求解这一复杂系统的关键步骤和技术细节,如直流潮流用于电网建模、气网的压力-流量关系线性化处理、热网的温度传递延迟模型等。此外,还讨论了模型的目标函数设计、求解器配置及其性能表现,并强调了代码的高质量和模块化设计,确保了良好的可读性和扩展性。 适合人群:从事综合能源系统研究的技术人员、高校相关专业师生、对能源系统优化感兴趣的科研工作者。 使用场景及目标:适用于希望深入了解电-气-热综合能源系统耦合机制的研究者;可用于教学演示、项目开发、学术研究等领域,帮助使用者掌握复杂的多能源系统优化方法。 其他说明:代码中包含了详尽的注释和模块化设计,便于理解和维护;提供了真实的测试数据(如比利时20节点配气网络),增强了模型的实际应用价值。

    物流领域中基于遗传算法、蚁群算法和粒子群算法的带时间窗车辆路径优化(VRPTW)研究与MATLAB实现

    内容概要:本文详细探讨了带时间窗的车辆路径优化(VRPTW)问题及其在物流领域的应用。首先介绍了VRPTW的基本概念和问题背景,即在满足客户需求如时间窗、载重限制的前提下,寻找最优车辆行驶路径以最小化总行驶距离和成本。接着,文章深入讲解了几种常用的优化算法,包括遗传算法(GA)、蚁群算法(ACO)和粒子群算法(PSO),并通过MATLAB实现了这些算法的关键步骤。此外,还讨论了物流选址对车辆路径的影响,并提出了结合两者进行综合优化的方法。最后,通过对不同算法的实际测试,展示了它们各自的优缺点及应用场景。 适合人群:从事物流管理、运筹学研究的专业人士,以及对车辆路径优化感兴趣的科研人员和技术开发者。 使用场景及目标:适用于需要解决复杂物流配送问题的企业,旨在提高配送效率、降低成本、提升客户满意度。具体目标包括但不限于:减少车辆行驶距离、优化配送时间表、合理分配车辆资源等。 其他说明:文中提供了大量MATLAB代码示例,帮助读者更好地理解和实现相关算法。同时强调了时间窗处理不应采用硬约束而应加入适当的惩罚项,以避免算法无法找到可行解的情况发生。

Global site tag (gtag.js) - Google Analytics