题意:判断最小生成树是否唯一
思路:第一次用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
分享到:
相关推荐
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
### POJ1679 TheUniqueMST **题目链接:** <http://acm.pku.edu.cn/JudgeOnline/problem?id=1679> **核心知识点:** - **问题描述:** 验证给定图的最小生成树是否唯一。 - **解题思路:** 可以先通过Prim或...
【标题】"POJ 1679 练习克鲁斯卡尔Kruskal算法" 在图论领域,克鲁斯卡尔(Kruskal)算法是一种用于解决最小生成树问题的有效方法。这个问题涉及到在一个加权无向图中找到一棵包括所有顶点的树,其边的权重之和尽...
poj 1611 The Suspects 代码 并查集的应用
【标题】"POJ1426-Find The Multiple【BFS+同余模】"是一道来源于北京大学在线编程平台POJ的算法题目,主要涉及到了广度优先搜索(BFS)与同余模运算的知识点。这道题目要求解决的是寻找一个整数的倍数问题,可能...
【标题】"POJ1027 - The Same Game"是一个经典的编程竞赛题目,源自北京大学的在线编程平台POJ(Problem Online Judge)。该题目主要考察的是动态规划和矩阵链乘法的知识,要求参赛者编写程序解决一个具有策略性的...
标题中的“POJ 1054 The Troublesome Frog”是一个编程竞赛题目,来源于“Programming Online Judge”(POJ)平台。这个平台是程序员们练习算法和编程技能的地方,通常涉及各种数据结构和算法的问题。题目...
poj 1611 The Suspects.md
3. **P1679(Unique_MST_prim).cpp 和 P1679(Unique_MST_kruskal).cpp** - 这两个文件都涉及了“唯一最小生成树”问题。Prim和Kruskal是两种常见的求解最小生成树的算法。在某些情况下,图可能有唯一的最小生成树...
poj 3191 The Moronic Cowmpouter.md
poj 1989 The Cow Lineup.md
poj 3260 The Fewest Coins.md
poj 3901 The Computer Game.md
北大POJ1163-The Triangle
【标题】"POJ1163 - The Triangle" 是北京大学在线编程平台POJ上的一道算法题目。这道题目通常被归类为计算机科学与信息技术领域的算法问题,特别是涉及数据结构和动态规划的子领域。 【描述】该题目的解题报告详细...
标题“POJ2151-Check the difficulty of problems”是指一个编程竞赛题目,来源于北京大学的在线判题系统POJ(PKU Online Judge)。这个题目要求参赛者编写程序来评估问题的难度。描述中的“解题报告+AC代码”表明...
《POJ2983-Is the Information Reliable:解析差分约束与优化Bellman算法》 北京大学在线编程平台上的POJ2983题目——"Is the Information Reliable",是一道涉及差分约束系统(Differential Constraint System)与...
北大POJ3267-The Cow Lexicon
【标签】"POJ 3982 The Fibonacci sequence"是这个编程问题的标识,便于搜索和分类。POJ平台上的每个题目都有唯一的标签,方便用户查找和回顾。 斐波那契序列是计算机科学中一个基础而重要的概念,它的定义如下:...