CCF CSP 201812-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
样例说明

1.问题本质为找最小生成树的最大边。
2.考试时，错误地使用了Prim算法，不仅实现复杂，而且最后还超时了，只得了50分。
3.正确解答方法为，Krustkal算法+并查集，实现非常简单。
4.有关算法可自行百度，有些博客已经写得非常清楚了。
并查集

以下为解题代码。
Kruskal+并查集：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=1000000;
int prt[maxn];
struct edge{
	int v;
	int u;
	int t;
}; 
bool cmp(edge const &A,const edge &B)
{
	return A.t<B.t;
}
void init(int n)//初始化 
{
	for(int i=1;i<=n;++i)
		prt[i]=i;
}
int find(int x)//查 
{
	while(prt[x]!=x)
	{
		prt[x]=prt[prt[x]];
		x=prt[x];
	}
	return x;
}
bool joint(int x,int y)//并 
{
	int fx=find(x);
	int fy=find(y);
	if(fx==fy)
		return false;
	else
		{
			prt[fx]=fy;
			return true;
		}
}
vector<edge>E;
int main()
{
	int n,m,r;
	int cnt=0,ans=0;
	cin>>n>>m>>r;
	for(int i=0;i<m;++i)
	{
		edge Temp;
		cin>>Temp.v>>Temp.u>>Temp.t;
		E.push_back(Temp);
	}
	sort(E.begin(),E.end(),cmp);
	init(n);
	for(int i=0;i<m;++i)
	{
		if(joint(E[i].v,E[i].u))
		{
			cnt++;
			ans=E[i].t;//因为边长已排好序 
		}
		if(cnt==n-1)
			break;
	}
	cout<<ans;
}

Prim算法（本题时间超限）：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=500;
const long long INF=1<<30;
int visit[maxn]={false};
vector<int> vi;
struct Node{
	int id;
	long long wgt;
};
vector< vector<Node> >G(maxn);//图 ，用领接表表示 
int n; //节点数 
int len=0;//总长度，该题不需要 
int maxe=0;//最长边 
void prim(int s)//输入为源点,根节点。 
{
	visit[s]=true;
	vi.push_back(s);
	for(int i=0;i<n-1;i++)
	{
		int u=-1;
		long long MIN=INF;
		for(int j=0;j<vi.size();++j)
		{
			for(int k=0;k<G[k].size();++k)//贪心 
			{
				Node N=G[vi[j]][k];
				if(visit[N.id])
					continue;
				if(N.wgt<MIN)
					{
						MIN=N.wgt;
						u=N.id; 
					}
			}
		}
		if(-1==u)
			return ;
		len+=MIN;
		if(MIN>maxe)
			maxe=MIN;
		visit[u]=true;
		vi.push_back(u);
		
	 } 	
}

int main()
{
	int m,r;
	cin>>n>>m>>r;
	for(int i=0;i<m;++i)
	{
		int v,u,t;
		Node N1,N2;
		cin>>v>>u>>t;
		N1.id=u;
		N1.wgt=t;
		N2.id=v;
		N2.wgt=t;
		G[v].push_back(N1);
		G[u].push_back(N2);
	}
	prim(r);
	cout<<maxe;
}