直接上代码,~ ~
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
const int Inf = 0x3f3f3f3f, maxn = 5000 + 5, maxm = 400000 + 5;
int pre[maxn], paths[maxm];//paths[]用来间接排序
struct Point{
int pta = 0, cost = Inf, done = false;
}point[maxn];
struct Path{
int next = 0, weight = 0, ends = 0, begins = 0;
}path[maxm];
int e = 1;
void made (int u, int v, int p)//建边 (图)
{
path[e].begins = u;
path[e].ends = v;
path[e].weight = p;
path[e].next = point[u].pta;//邻接表
point[u].pta = e++;
//无向图,建两次
path[e].begins = v;
path[e].ends = u;
path[e].weight = p;
path[e].next = point[v].pta;
point[v].pta = e++;
}
//并查集
int findd (int x)//查找函数的递归实现 (包含路径压缩)
{
return pre[x] == x ? //是否查找到根节点
x : //已为根节点 :返回根节点的值
pre[x] = findd (pre[x]);//不为根节点 :继续查找,返回查找到的(根节点)的值
}
bool joinn (int a, int b)//相通返回真
{
int x1 = findd(a), x2 = findd(b);
if (x1 == x2)
return true;
pre[x1] = x2;
return false;
}
//间接排序函数:将边的序号按照边的权值排序
bool cmp(int a, int b){
return path[a].weight < path[b].weight;
}
int main()
{
cin >> n >> m;
//初始化
long long res = 0;
for (int i = 1; i <= n; i++)
pre[i] = i;
for (int i = 1; i <= (m<<2); i++)
paths[i] = i;
//读入及建边(图)
for (int i = 1; i <= m; i++ )
{
int a, b, c;
cin >> a >> b >> c;
made (a, b, c);
}
m <<= 1;//建无向图,边数加倍
sort(paths + 1, paths + m + 1, cmp);//间接排序 :边
for(int i = 1; i <= m; ++i)//第二步:连接点
if(! joinn( path[paths[i]].begins, path[paths[i]].ends )){//该边连接的两点不在一个集合中
res += path[paths[i]].weight;//将该边添加至生成树中
// cout << res <<endl;
}
bool ok = true;
for(int i = 1; i < n && ok; i++)
if(pre[i] != pre[i+1]) ok = false;//判联通
if(ok) cout<<res;
else cout<<"orz";
return 0;
}