http://acm.nyist.net/JudgeOnline/problem.php?pid=118次小生成树

本文主要是介绍http://acm.nyist.net/JudgeOnline/problem.php?pid=118次小生成树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

昨天做的次小生成树的用的是标记法，，，今天用的的是，，，，添边，删边法，，

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 501
#define M 9999999
#define MM -999999
using namespace std;
int map[N][N],maxs[N][N],dist[N];
bool visit[N];
int n,m;
bool prim()
{    int  pre[N]={0};int now=1;dist[now]=0;visit[now]=false;for(int i=2;i<=n;++i){ visit[i]=true;dist[i]=map[now][i];pre[i]=now;}for(int i=1;i<n;++i){    int minx=M;for(int j=1;j<=n;++j)if(visit[j]&&dist[j]<minx)minx=dist[now=j];visit[now]=false;int pr=pre[now];maxs[pr][now]=maxs[now][pr]=map[pr][now];for(int j=1;j<=n;++j) 记录到生成树中的各个顶点最大边权，，，if(!visit[j])maxs[j][now]=max(maxs[j][pr],maxs[now][pr]);for(int j=1;j<=n;++j)if(visit[j]&&dist[j]>map[now][j])dist[j]=map[now][j],pre[j]=now;}for(int j=1;j<=n;++j)for(int i=1;i<=n;++i){if(pre[i]==j||pre[j]==i) continue;else if(maxs[j][i]==map[i][j]) return true;判断加入的边，和删除的边的大小关系，，，}return false;
}
int main()
{ int Case;cin>>Case;while(Case--){    cin>>n>>m;for(int j=1;j<=n;++j)for(int i=1;i<=n;++i){map[i][j]=M;maxs[i][j]=MM;}for(int i=1;i<=m;++i){    int a,b,c;cin>>a>>b>>c;if(map[a][b]>c)map[a][b]=map[b][a]=c;}if(prim()) cout<<"Yes"<<endl;else  cout<<"No"<<endl;}   return 0;}

这篇关于http://acm.nyist.net/JudgeOnline/problem.php?pid=118次小生成树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---