CCF201812-4 数据中心
题目
试题编号: 201812-4
试题名称: 数据中心
时间限制: 1.0s
内存限制: 512.0MB
问题描述:
样例输入
4
5
1
1 2 3
1 3 4
1 4 5
2 3 8
3 4 2
样例输出
4
样例说明
分析:直接求最小生成树。
先将存放边信息的容器进行排序,然后判断点是否每次输入含有重复,再判断是否生成回路(即p=q)。生成回路则放弃这条边顺序往下走,不生成回路判断是否包含所有节点并且满足树的条件,满足则退出。
开始做这个超时了只有分50分,原因在于原来用的C++的find函数(暴力查找匹配),后面用一个标志位数组代替即可解决超时问题。
#include<bits/stdc++.h>
using namespace std;
struct KES{
int a;
int b;
int c;
};
bool Comp(const KES& Z, const KES& Y) {
return Z.c < Y.c;
}
const int maxn=5*1e5+10;
int f[maxn]; //标志位数组
int main(){
KES X[100000];
int n,m,root,result,length=0,size,bian=0;
vector<int> dian;
scanf("%d%d%d",&n,&m,&root);
for(int i=0;i<m;i++)
scanf("%d%d%d",&X[i].a,&X[i].b,&X[i].c);
sort(X,X+m,Comp);
memset(f,0,sizeof(f));//初始化标志数组
for(int i=0;i<m;i++)
{
if(f[X[i].a]<=0)//表示没有
{
dian.push_back(X[i].a);
f[X[i].a]=1;
}
if(f[X[i].b]<=0)//表示没有
{
dian.push_back(X[i].b);
f[X[i].b]=1;
}
size=dian.size();
bian++;
if(bian==size)//出现回路
{bian--;
if(size==(length+1))
dian.pop_back();
else if(size==(length+2))
{dian.pop_back();
dian.pop_back();
}
continue;
}
//未出现回路
length=size;
if(length==n&&length==(bian+1))
{
result=X[i].c;
break;
}
}
printf("%d\n",result);
return 0;
}