本文主要是介绍ural 1160,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
最小生成树 第一次敲 套用几个函数 其实挺容易的
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
struct node
{int u,v,w;void f(int a, int b, int c){u = a;v = b;w = c;}bool operator < (const node & e) const{return w < e.w;}
};
vector<node>q,qq;
int p[2000],r[2000];int findd(int x)
{return p[x] == x ? x : p[x] = findd(p[x]);
}
int main()
{int n,m;node cc;scanf("%d%d",&n,&m);for(int i = 0; i < m; i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);cc.f(a,b,c);q.push_back(cc);}sort(q.begin(), q.end());int ans = 0;for(int i = 0; i <= n; i++)p[i] = i;for(int i = 0; i < m; i++){int x = findd(q[i].u), y = findd(q[i].v);if(x != y){ans = q[i].w;qq.push_back(q[i]);p[x] = y;}}printf("%d\n",ans);int len = qq.size();printf("%d\n",len);for(int i = 0; i < len; i ++)printf("%d %d\n",qq[i].u,qq[i].v);return 0;
}
这篇关于ural 1160的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!