题目链接:

https://vjudge.net/problem/POJ-1679

题目大意:

给定一个无向连通网,判断最小生成树是否唯一。

思路:

(1)对图中的每条边,扫描其他边,如果存在相同权值的边,对该边做标记。

(2)然后用kruskal算法或者prim算法求MST(标记MST中的边)

(3)求得MST后,如果MST中未包含做了标记的边,那么MST唯一。

MST中不包含未标记的边,说明MST中没有那些权值相同的边,用kruskal算法可知,该最小生成树肯定唯一。

(4)如果包含标记的边,依次去掉这些边,再求MST,如果所求的MST权值和之前的MST权值一样说明最小生成树不唯一,反之,则唯一。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<sstream>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + ;
const int INF = << ;
int dir[][] = {,,,,-,,,-};
int T, n, m, x;
bool first;
struct edge
{
int u, v, w;
bool used, equal, del;//used表示是否在MST中,equal表示边是否是相等,del表示求MST中删除的边
bool operator <(const edge& a)const
{
return w < a.w;
}
};
edge a[maxn];
int par[], high[];
//初始化n个元素
void init(int n)
{
for(int i = ; i < n; i++)
{
par[i] = i;
high[i] = ;
}
}
//查询树的根
int Find(int x)
{
return par[x] == x ? x : par[x] = Find(par[x]);//路径压缩
}
void unite(int x, int y)
{
x = Find(x);
y = Find(y);
if(x == y)return;
if(high[x] < high[y])par[x] = y;//y的高度高,将x的父节点设置成y
else
{
par[y] = x;
if(high[x] == high[y])high[x]++;
}
}
int kruskal(int n, int m)//点数n,边数m
{
int sum_mst = ;//mst权值
int num= ;//已经选择的边的边数
sort(a, a + m);//边进行排序
init(n);//初始化并查集
for(int i = ; i < m; i++)
{
int u = a[i].u;
int v = a[i].v;
if(a[i].del)continue;
if(Find(u - ) != Find(v - ))//图最开始的下标是1,并查集是0
{
//printf("%d %d %d\n", u, v, a[i].w);
sum_mst += a[i].w;
num++;
unite(u - , v - );
if(first)a[i].used = ;//标记第一次MST的边
}
if(num >= n - )break;
}
//printf("weight of mst is %d\n", sum_mst);
return sum_mst;
}
int main()
{
cin >> T;
while(T--)
{
cin >> n >> m;
for(int i = ; i < m; i++)
{
cin >> a[i].u >> a[i].v >> a[i].w;
a[i].used = a[i].equal = a[i].del = ;
}
sort(a, a + m);
for(int i = ; i < m; i++)//标记权值相同的边
{
int j = i + ;
for(; j < m; j++)
{
if(a[j].w == a[i].w)a[i].equal = a[j].equal = ;
else break;
}
i = j - ;
}
first = ;
int mst1 = kruskal(n, m);
first = ;
int flag = ;
for(int i = ; i < m; i++)
{
if(a[i].used && a[i].equal)//依次删除第一次MST中相等的边,再次求MST
{
a[i].del = ;
int mst2 = kruskal(n, m);
if(mst1 == mst2)
{
flag = ;
cout<<"Not Unique!"<<endl;
break;
}
a[i].del = ;//删除的标记清除
}
}
if(!flag)cout<<mst1<<endl;
}
return ;
}

最新文章

  1. jQuery的案例及必知重要的jQuery选择器
  2. Cocos学习-----Cocos2Dx安装
  3. 【mysql】关于乐观锁
  4. DOM Element节点类型详解
  5. SQLServer2012自增列值跳跃的问题
  6. 安装redis时遇到zmalloc.h:50:31: 致命错误:jemalloc/jemalloc.h:没有那个文件或目录
  7. windows 服务安装脚本拾遗
  8. SVN 主干(trunk)、分支(branch )、标记(tag)
  9. JavaScriptSerializer.MaxJsonLength属性问题
  10. vim 文字插入
  11. Java [Leetcode 122]Best Time to Buy and Sell Stock II
  12. Android getTopActivity的方法
  13. POJ 1659 Frogs&amp;#39; Neighborhood(度序列组成)
  14. Oracle 用户操作表权限
  15. 让 IE支持圆角的方法
  16. php查询mysql中的json编码后的字符串内容的方法
  17. 图片人脸检测——OpenCV版(二)
  18. R 简明教程
  19. java.lang.IndexOutOfBoundsException: setSpan (35 ... 35) ends beyond length 28
  20. ASM下裸设备的路径更改是否会影响数据库的执行

热门文章

  1. Web API返回JSON数据
  2. Linux学习笔记之——基础命令学习
  3. (转)MySQL配置文件mysql.ini参数详解、MySQL性能优化
  4. cocos2dx中创建动画的三种方法
  5. Nested Loop,Sort Merge Join,Hash Join
  6. java String 去除空格
  7. [CSAPP笔记][第八章异常控制流][呕心沥血千行笔记]
  8. 编写简单的爬虫从流行的Scrapy 框架讲起
  9. org.hibernate.AnnotationException: mappedBy reference an unknown target entity property: com.entity.annotations.House.district in
  10. As a Start - 毫厘之间,宇宙之外
  11. SkyReach 团队团队展示
  12. IP地址及网络常识
  13. SpringCloud教程 | 第四篇:断路器(Hystrix)
  14. python 基础 ------字符串的调用详解(1)
  15. Java IO--NIO(二)
  16. IDEA VM设置
  17. nopCommerce 3.2新功能
  18. 总结几个常用的系统安全设置(含DenyHosts)
  19. MySQL数据库的学习
  20. [UE4]虚幻4链接独立服务器