# 11234: 【原1234】Kruskal

### 题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1234

## Sample Input

``````6 10
1 2 6
1 4 5
1 3 1
2 3 5
3 4 5
2 5 3
3 5 6
3 6 4
4 6 2
5 6 6
``````

## Sample Output

``````15              //P366的例子
``````

## Limits

0<n<=10000 0<=m<=100000

## ligongzzz's solution

``````#include "iostream"
#include "cstdio"
#include "cstring"
using namespace std;

template <class T, class T_val = decltype(*declval<T>()),
class Compare = bool (*)(T_val, T_val)>
void quick_sort(T start, T end,
Compare cmp = [](T_val a, T_val b) {return a < b; }) {
if (start == end)
return;
auto i = start, j = end;
--j;
if (i == j)
return;
//交换
auto key = *start;
for (bool status = true; i != j;) {
if (status) {
if (cmp(*j, key)) {
*i = *j;
++i;
status = false;
}
else
--j;
}
else {
if (cmp(key, *i)) {
*j = *i;
--j;
status = true;
}
else
++i;
}
}
*i = key;
//递归
quick_sort(start, ++i, cmp);
quick_sort(i, end, cmp);
}

class edge {
public:
int from = 0, to = 0;
int length = 0;
};

edge edges[100009];

//并查集
class disjointSet {
public:
//数组
int* parent;
int length = 0;

//构造函数
disjointSet() = default;
disjointSet(int size) :length(size) {
parent = new int[size];
memset(parent, -1, length * sizeof(int));
}

//析构函数
~disjointSet() {
length = 0;
delete[] parent;
}

//寻找
int find_root(int x) {
int temp = x;
for (; parent[temp] >= 0; temp = parent[temp]);
//压缩路径
for (int i = x; i != temp;) {
int tempi = parent[i];
parent[i] = temp;
i = tempi;
}
return temp;
}
//合并
void set_union(int root1, int root2) {
if (root1 == root2)
return;
if (parent[root1] > parent[root2]) {
parent[root2] += parent[root1];
parent[root1] = root2;
}
else {
parent[root1] += parent[root2];
parent[root2] = root1;
}
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int n, m;
cin >> n >> m;

disjointSet set_data(n + 1);

for (int i = 0; i < m; ++i) {
cin >> edges[i].from >> edges[i].to >> edges[i].length;
}

quick_sort(edges, edges + m, [](edge a, edge b) {return a.length < b.length; });

int cnt = 0;
long long ans = 0;
int root_pos = edges[0].from;
for (int i = 0; i < m; ++i) {
if (set_data.find_root(edges[i].from) != set_data.find_root(edges[i].to)) {
set_data.set_union(set_data.find_root(edges[i].from), set_data.find_root(edges[i].to));
++cnt;
ans += edges[i].length;
}
if (cnt == n - 1) {
break;
}
}

cout << ans;

return 0;
}
``````

## Neight99's solution

``````#include <iostream>

using namespace std;

const int maxN = 1e4 + 100;
const int maxM = 1e5 + 100;

struct edge {
int beg;
int end;
int weight;
};

class DisjointSet {
private:
int size;
int *parent;

public:
DisjointSet(int s);
~DisjointSet() { delete[] parent; }
void Union(int root1, int root2);
int Find(int x);
};

DisjointSet::DisjointSet(int n) : size(n) {
parent = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = -1;
}
}

int DisjointSet::Find(int x) {
if (parent[x] < 0) {
return x;
}
return parent[x] = Find(parent[x]);
}

void DisjointSet::Union(int root1, int root2) {
root1 = Find(root1);
root2 = Find(root2);
if (root1 == root2) {
return;
} else if (parent[root1] < parent[root2]) {
parent[root1] += parent[root2];
parent[root2] = root1;
} else {
parent[root2] += parent[root1];
parent[root1] = root2;
}
}

edge e[maxM];
int ans = 0, n, m;

void qSort(edge *, int, int);

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

cin >> n >> m;

DisjointSet ds(n + 10);

for (int i = 1; i <= m; i++) {
int temp1, temp2, temp3;
cin >> temp1 >> temp2 >> temp3;
e[i].beg = temp1;
e[i].end = temp2;
e[i].weight = temp3;
}

qSort(e, 1, m);

for (int i = 1; i <= m; i++) {
int from = e[i].beg, to = e[i].end;
if (ds.Find(from) != ds.Find(to)) {
ds.Union(from, to);
ans += e[i].weight;
}
}

cout << ans;

return 0;
}

void qSort(edge *nums, int l, int h) {
if (l >= h) {
return;
}
int first = l, last = h, wmid = e[(first + last) / 2].weight;
while (first <= last) {
while (e[first].weight < wmid) {
first++;
}
while (e[last].weight > wmid) {
last--;
}
if (first <= last) {
edge temp = e[last];
e[last] = e[first];
e[first] = temp;
first++;
last--;
}
}
qSort(nums, l, last);
qSort(nums, first, h);
}
``````

## yyong119's solution

``````#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;
typedef struct{
int v[3];
} Tm;
bool comp(Tm a, Tm b) {
return a.v[0] < b.v[0];
}
Tm edge[100001];
int n, m, cost, addin, tail, x, y;
int father[100001];

int getfather(int f) {
if (father[f] == f) return f;
else {
father[f] = getfather(father[f]);
return father[f];
}
}
void unionxy(int x, int y) {
father[x] = y;
}

int main() {

scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) father[i] = i;
for (int i = 1; i <= m; i++) scanf("%d%d%d", &edge[i].v[1], &edge[i].v[2], &edge[i].v[0]);
sort(edge + 1, edge + m + 1, comp);
while (addin < n - 1) {
tail++; x = getfather(edge[tail].v[1]); y = getfather(edge[tail].v[2]);
if (x == y) continue;
unionxy(x, y);
cost += edge[tail].v[0];
}
printf("%d\n", cost);
return 0;
}
``````

## Zsi-r's solution

``````#include <iostream>
using namespace std;

template <class typeofver, class typeofedge>
{
public:
void insert(typeofver x, typeofver y, typeofedge w);
int kruskal() const;

private:
struct kruskalEdge
{
int beg, end;
typeofedge w;
bool operator<(const kruskalEdge &rp) const { return w < rp.w; }
};
struct edgeNode
{
int end;
typeofedge weight;
edgeNode *next;

edgeNode(int e, typeofedge w, edgeNode *n = NULL)
{
end = e;
weight = w;
next = n;
}
};
struct verNode
{
typeofver ver;

verNode(edgeNode *h = NULL) { head = h; }
};

int Vers, Edges;
verNode *verList;
int find(typeofver v) const
{
for (int i = 0; i < this->Vers; i++)
if (verList[i].ver == v)
return i;
}
};

template <class Type>
class priorityQueue
{
public:
priorityQueue(int capacity = 10);
priorityQueue(const Type data[],int size);
~priorityQueue();
bool isEmpty()const;
void enQueue(const Type &x);
Type deQueue();
private:
int currentSize;
Type *array;//array[0]不放东西
int maxSize;

void doubleSpace();
void buildHeap();//对一串数字进行有序化建堆
void percolateDown(int hole);
};

template <class Type>
priorityQueue<Type>::priorityQueue(int capacity)
{
array = new Type[capacity];
maxSize = capacity;
currentSize = 0;
}

template <class Type>
priorityQueue<Type>::~priorityQueue()
{
delete[] array;
}

template <class Type>
bool priorityQueue<Type>::isEmpty() const
{
return currentSize == 0;
}

template <class Type>
{
return array[1];
}

template <class Type >
void priorityQueue<Type>::enQueue(const Type &x)
{
if (currentSize == maxSize-1)//因为array[0]不放东西
doubleSpace();

//向上过滤
int hole = ++currentSize;
for (; hole > 1 && x < array[hole / 2]; hole /= 2)
array[hole] = array[hole / 2];
array[hole] = x;
}

template <class Type >
Type priorityQueue<Type >::deQueue()
{
Type miniItem;
miniItem = array[1];
array[1] = array[currentSize--];//把最大(maybe)的数放在第一个，再向下过滤
percolateDown(1);
return miniItem;
}

template<class Type >
void priorityQueue<Type >:: percolateDown(int hole)//向下过滤
{
int child;
Type tmp = array[hole];
for (; hole * 2 <= currentSize; hole = child){
child = hole * 2;
if (child!=currentSize && array[child+1]<array[child])//找小的儿子，如果child==currentSize，则没有右儿子
child++;
if(array[child]<tmp)
array[hole] = array[child];
else
break;
}
array[hole] = tmp;
}

template <class Type >
void priorityQueue<Type >::buildHeap()
{
for (int i = currentSize / 2; i > 0;i--)
percolateDown(i);
}

template <class Type>
priorityQueue<Type>::priorityQueue(const Type *items, int size) : maxSize(size + 10), currentSize(size)
{
array = new Type[maxSize];
for (int i = 0; i < size;i++)
array[i + 1] = items[i];
buildHeap();
}

template <class Type >
void priorityQueue<Type >::doubleSpace()
{
Type *tmp = array;
maxSize *= 2;
array = new Type[maxSize];
for (int i = 0; i <= currentSize; i++) //当currentSize == maxSize-1时，调用doubleSpace()
array[i] = tmp[i];
delete[] tmp;
}

class DisjointSet{
private:
int size;
int *parent;
public:
DisjointSet(int s);
~DisjointSet() { delete[] parent; }
void Union(int root1, int root2);
int Find(int x);
};

DisjointSet::DisjointSet(int s)
{
size = s;
parent = new int[size];
for (int i = 0; i < size;i++)
parent[i] = -1;
}

int DisjointSet::Find(int x)
{
if (parent[x]<0)
return x;
return parent[x] = Find(parent[x]);
}

void DisjointSet::Union(int root1,int root2)
{
if (root1==root2)
return;
if (parent[root1]>parent[root2])
{
parent[root2] += parent[root1];
parent[root1] = root2;
}
else
{
parent[root1] += parent[root2];
parent[root2] = root1;
}
}

template <class typeofver, class typeofedge>
{
this->Vers = vSize;

verList = new verNode[vSize];
for (int i = 0; i < vSize;i++)
{
verList[i].ver = i+1;
}
}

template<class typeofver,class typeofedge>
{
int i;
edgeNode *p;

for (i = 0; i < this->Vers;i++)
{
delete p;
}
delete[] verList;
}

template <class typeofver,class typeofedge>
void adjListGraph<typeofver ,typeofedge>::insert(typeofver x,typeofver y,typeofedge w)
{
int u = find(x), v = find(y);
++this->Edges;
}

template<class typeofver,class typeofedge>
{
int count = 0;
int edgesAccepted = 0, u, v;
edgeNode *p;
kruskalEdge e;
DisjointSet ds(this->Vers);
priorityQueue<kruskalEdge> pq;

//生成优先级队列
for (int i = 0; i < this->Vers;i++)
{
for (p = verList[i].head; p != NULL; p = p->next)
if (i<p->end)
{
e.beg = i;
e.end = p->end;
e.w = p->weight;
pq.enQueue(e);
}
}

//开始归并
while(edgesAccepted<(this->Vers)-1)
{
e = pq.deQueue();
u = ds.Find(e.beg);
v = ds.Find(e.end);
if(u!=v){
edgesAccepted++;
count += e.w;
ds.Union(u, v);
}
}
return count;
}

int main()
{
int numofver, numofedge,weight,node1,node2,tmp;
cin >> numofver >> numofedge;
for (int i = 0; i < numofedge;i++)
{
cin >> node1 >> node2 >> weight;
if (node1>node2){
tmp = node2;
node2 = node1;
node1 = tmp;
}
gf.insert(node1, node2, weight);
}
cout << gf.kruskal() << endl;
return 0;
}
``````