`

POJ1679 The Unique MST

    博客分类:
  • MST
MST 
阅读更多

题意:判断最小生成树是否唯一

思路:第一次用kruskal求出最小生成树,记为ans,然后依次去除已经选进来的边,进行kruskal,如果ans==kruskal()的话,则输出不唯一。

注意:1.第一次求kruskal时记得要先判断是否能生成最小生成树(但是我没判断就A了。。理论上来说是要判断的。。)

2.注意存放变的数组开大一点。我用G++交了几次一直WA,原代码改成C++交就RE,然后数组改了下大小就A了。被G++坑死了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 20005
#define inf 1<<28
using namespace std;

struct kdq
{
    int s,e,l;
} road[Max];
int f[Max];
bool visit[Max];
bool visit1[Max];
int n,m;

bool cmp(kdq x,kdq y )
{
    return x.l<y.l;
}

int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}

void Union(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)return ;
    if(y>x)
        f[y]=x;
    else
        f[x]=y;
}

int kruskal(int d)//d是用来删除边的
{
    int num=0;
    int num1=0;
    for(int i=0; i<m; i++)
    {
        if(i!=d)
        {
            int x=find(road[i].s);
            int y=find(road[i].e);
            if(y!=x)
            {
                num1++;
                Union(x,y);
                num+=road[i].l;
                visit[i]=1;//记录第一次取来的边的标号
            }
        }
    }
    if(num1==n-1)//判断能生成最小生成树
    return num;
    else
    return -1;
}

int main()
{
    int i,j,k,l,T;
    cin>>T;
    while(T--)
    {
        memset(visit,0,sizeof(visit));
        cin>>n>>m;
        for(i=0; i<=n; i++)
            f[i]=i;
        for(i=0; i<m; i++)
            scanf("%d%d%d",&road[i].s,&road[i].e,&road[i].l);
        sort(road,road+m,cmp);
        int ans=kruskal(-1);
        for(i=0; i<m; i++)
            visit1[i]=visit[i];//将第一标记的序号存入visit1[],因为visit[]在接下来的kruskal中还会改变
        if(ans==-1)//这个判断不需要也可以过。。难道是数据水了?
        {
            cout<<0<<endl;
            continue;
        }
        bool flag=0;
        for(i=0; i<m; i++)
        {
            if(visit1[i])//如果是第一次取到的边
            {
                for(j=0; j<=n; j++)
                    f[j]=j;
                if(kruskal(i)==ans)//如果删除了这条边后,最小生成树的值相等,则说明不唯一
                {
                    flag=1;
                    break;
                }
            }
        }
        if(flag)
            cout<<"Not Unique!"<<endl;
        else
            cout<<ans<<endl;
    }
    return 0;
}


更多详细信息请查看java教程网 http://www.itchm.com/forum-59-1.html
分享到:
评论

相关推荐

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

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

    poj pku图论、网络流入门题总结、汇总

    ### POJ1679 TheUniqueMST **题目链接:** &lt;http://acm.pku.edu.cn/JudgeOnline/problem?id=1679&gt; **核心知识点:** - **问题描述:** 验证给定图的最小生成树是否唯一。 - **解题思路:** 可以先通过Prim或...

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

    【标题】"POJ 1679 练习克鲁斯卡尔Kruskal算法" 在图论领域,克鲁斯卡尔(Kruskal)算法是一种用于解决最小生成树问题的有效方法。这个问题涉及到在一个加权无向图中找到一棵包括所有顶点的树,其边的权重之和尽...

    poj 1611 The Suspects 代码

    poj 1611 The Suspects 代码 并查集的应用

    POJ1426-Find The Multiple【BFS+同余模】

    【标题】"POJ1426-Find The Multiple【BFS+同余模】"是一道来源于北京大学在线编程平台POJ的算法题目,主要涉及到了广度优先搜索(BFS)与同余模运算的知识点。这道题目要求解决的是寻找一个整数的倍数问题,可能...

    POJ1027-The Same Game

    【标题】"POJ1027 - The Same Game"是一个经典的编程竞赛题目,源自北京大学的在线编程平台POJ(Problem Online Judge)。该题目主要考察的是动态规划和矩阵链乘法的知识,要求参赛者编写程序解决一个具有策略性的...

    POJ 1054 The Troublesome Frog.rar

    标题中的“POJ 1054 The Troublesome Frog”是一个编程竞赛题目,来源于“Programming Online Judge”(POJ)平台。这个平台是程序员们练习算法和编程技能的地方,通常涉及各种数据结构和算法的问题。题目...

    poj 1611 The Suspects.md

    poj 1611 The Suspects.md

    Poj中的一些题目源代码

    3. **P1679(Unique_MST_prim).cpp 和 P1679(Unique_MST_kruskal).cpp** - 这两个文件都涉及了“唯一最小生成树”问题。Prim和Kruskal是两种常见的求解最小生成树的算法。在某些情况下,图可能有唯一的最小生成树...

    poj 3191 The Moronic Cowmpouter.md

    poj 3191 The Moronic Cowmpouter.md

    poj 1989 The Cow Lineup.md

    poj 1989 The Cow Lineup.md

    poj 3260 The Fewest Coins.md

    poj 3260 The Fewest Coins.md

    poj 3901 The Computer Game.md

    poj 3901 The Computer Game.md

    北大POJ1163-The Triangle

    北大POJ1163-The Triangle

    POJ1163-The Triangle

    【标题】"POJ1163 - The Triangle" 是北京大学在线编程平台POJ上的一道算法题目。这道题目通常被归类为计算机科学与信息技术领域的算法问题,特别是涉及数据结构和动态规划的子领域。 【描述】该题目的解题报告详细...

    POJ2151-Check the difficulty of problems

    标题“POJ2151-Check the difficulty of problems”是指一个编程竞赛题目,来源于北京大学的在线判题系统POJ(PKU Online Judge)。这个题目要求参赛者编写程序来评估问题的难度。描述中的“解题报告+AC代码”表明...

    POJ2983-Is the Information Reliable【差分约束+优化Bellman】

    《POJ2983-Is the Information Reliable:解析差分约束与优化Bellman算法》 北京大学在线编程平台上的POJ2983题目——"Is the Information Reliable",是一道涉及差分约束系统(Differential Constraint System)与...

    北大POJ3267-The Cow Lexicon

    北大POJ3267-The Cow Lexicon

    POJ3982-The Fibonacci sequence

    【标签】"POJ 3982 The Fibonacci sequence"是这个编程问题的标识,便于搜索和分类。POJ平台上的每个题目都有唯一的标签,方便用户查找和回顾。 斐波那契序列是计算机科学中一个基础而重要的概念,它的定义如下:...

Global site tag (gtag.js) - Google Analytics