11234: 【原1234】Kruskal

题目

题目描述

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

Description

关于最小生成树想必大家已经掌握，这是图论中的一个重要的问题。

关于其算法，我们一共介绍了两种：1.从结点入手的prim算法 2.从边入手的kruskal算法

这两种算法的核心思想都是贪心法。

其中，kruskal算法在使用时似乎更加简单。所以我们现在要熟练一下kruskal算法。

现在给定无向图，求它的最小生成树，输出最小生成树上边的总权值的大小。

如果你感到迷茫，请复习一下书上P308的快速排序相关内容，P323开始的不相交集（并查集）的内容以及P367的kruskal算法的内容。

为简化题目，我们约定：用正整数1,2,3……n来表示每个结点的ID（编号），所有的边权都为非负整数。

Input Format

第1行：n m //正整数n ，代表图中结点的数量。非负整数m代表要图中无向边的数量。

第2行到第1+m行: a b p //每行两个整数：代表结点a到结点b有一条无向边（a<->b），权值为p

Output Format

一个整数，即最小生成树上边的总权值的大小。

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];
        addin++;
    }
    printf("%d\n", cost);
    return 0;
}

Zsi-r's solution

#include <iostream>
using namespace std;

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

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;
        edgeNode *head;

        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();
    Type getHead() const;
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>
Type priorityQueue<Type>::getHead() const
{
    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>
adjListGraph<typeofver, typeofedge>::adjListGraph(int vSize)
{
    this->Vers = vSize;

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

template<class typeofver,class typeofedge>
adjListGraph<typeofver,typeofedge>::~adjListGraph()
{
    int i;
    edgeNode *p;

    for (i = 0; i < this->Vers;i++)
        while((p=verList[i].head)!=NULL)
        {
            verList[i].head = p->next;
            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);
    verList[u].head = new edgeNode(v, w, verList[u].head);
    ++this->Edges;
}

template<class typeofver,class typeofedge>
int adjListGraph<typeofver,typeofedge>::kruskal()const
{
    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;
    adjListGraph<int, int> gf(numofver);
    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;
}