次小生成树题(k) poj1679The Unique MST
2024-08-31 10:43:08
http://poj.org/problem?id=1679
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{
int u,v,w; }e[];
int f[];
vector<int>vis;
bool cmp(node p,node q){
return p.w<q.w;
}
int find(int x){
return x==f[x]?x:f[x]=find(f[x]);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
int n,m,ans=;
vis.clear();
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
e[i].u=u;
e[i].v=v;
e[i].w=w;
}
sort(e+,e++m,cmp);
for(int i=;i<=n;i++)
f[i]=i;
for(int j=,i=;i<=m;i++){
int u=e[i].u,v=e[i].v;
int a=find(u),b=find(v);
if(a!=b){
f[a]=b;
j++;
ans+=e[i].w;
vis.push_back(i);
}
if(j==n-)
break;
}
int flag=;
for(int k=;k<vis.size();k++){
int sign=vis[k];
int ans1=;
for(int i=;i<=n;i++)
f[i]=i;
int j=;
for(int i=;i<=m;i++){
if(i!=sign){
int u=e[i].u,v=e[i].v;
int a=find(u),b=find(v);
if(a!=b){
f[a]=b;
ans1+=e[i].w;
j++;
}
if(j==n-)
break;
}
}
if(j==n-){
if(ans1==ans){
flag=;
break;
}
}
}
if(flag)
puts("Not Unique!");
else
printf("%d\n",ans); }
return ;
}
最新文章
- List Copy
- (转)关于java和web项目中的相对路径问题
- Elasticsearch template configuration
- thymeleaf 局部变量、属性优先级、注释
- SQL Server 2008安装和配置过程
- 【学习总结】OS X , IOS , IOS SDK , XCode之间的关系
- JavaScript一道面试题求y的值是? z 的值是? s的值是?
- JAVA与C#关于JSON序列化的比较
- 【转】Pjax是什么以及为什么推荐大家用
- mysql字符集编码乱码测试如下
- 错误处理try catch
- eclipse maven could not resolve archetype之类的错误
- .NET之EntityFramework框架运用
- docker占满linux磁盘根目录的解决办法
- Linux命令行快捷键及vim快捷方式
- tensorflow学习笔记一------下载安装,配置环境(基于ubuntu16.04 pycharm)
- TextView显示内容不全
- hive使用map字段
- Kubernetes学习之路(二十四)之Prometheus监控
- 华为笔试——C++字符串四则运算的实现