ukruskal.cpp

该文件夹包含一系列常用的贪婪算法集合

#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

ifstream cin("in.txt");
ofstream cout("out.txt");
//---------------------------------------------------------------------------
class Disjoint_Set
{
    int n;
    int *A;
public:
    Disjoint_Set(int m);
    ~Disjoint_Set();
    void Union(int x, int y);
    int Find(int x);
    void Print()
    {
        for (int i = 0; i < n; i++)
            cout << A[i] << "\t";
        cout << endl;
        for (int i = 0; i < n; i++)
            cout << i << "\t";
        cout << endl;
    }
};

Disjoint_Set::Disjoint_Set(int m): n(m)
{
    A = new int[n];
    for (int i = 0; i < n; i++)
        A[i] = -1;
}

inline Disjoint_Set::~Disjoint_Set()
{
    delete [] A;
}

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

void Disjoint_Set::Union(int x, int y)
{
    int rx = Find(x);
    int ry = Find(y);
    if (rx != ry)
    {
        if (A[rx] < A[ry])
            A[ry] = rx;
        else
        {
            if (A[rx] == A[ry])
                A[ry]--;
            A[rx] = ry;
        }
    }
}
//---------------------------------------------------------------------------
struct Edge
{
    int v1, v2;
    int length;
    bool x;
    Edge(int a, int b, int len): v1(a), v2(b), length(len), x(false) {}
};

bool operator<(const Edge& a, const Edge& b)
{
    return a.length <  b.length;
}
//---------------------------------------------------------------------------
class MST
{
    int **M;
    int n;
    vector<Edge> A;
    void Print();
public:
    MST(int **mm, int nn): M(mm), n(nn)
    {
        for (int i = 0; i < n - 1; i++)
            for (int j = i + 1; j < n; j++)
                if (M[i][j] > 0)
                    A.push_back(Edge(i, j, M[i][j]));
    }
    void Kruskal()
    {
        sort(A.begin(), A.end());
        Disjoint_Set s(n);
        s.Union(A[0].v1, A[0].v2);
        A[0].x = true;
        int k = 1;
        for (int i = 1; i < n - 1; i++)
        {
            while (s.Find(A[k].v1) == s.Find(A[k].v2))
                k++;
            A[k].x = true;
            s.Union(A[k].v1, A[k].v2);
            k++;
        }
        Print();
    }
};

void MST::Print()
{
    for (int i = 0; i < A.size(); i++)
        if (A[i].x)
            cout    << char('a' + A[i].v1) << "\t"
                    << char('a' + A[i].v2) << "\t"
                    << A[i].length << endl;
}

int main(int argc, char* argv[])
{
    int **m;
    int n;
    cin >> n;
    m = new int*[n];
    for (int i = 0; i < n; i++)
    {
        m[i] = new int[n];
        for (int j = i + 1; j < n; j++)
            cin >> m[i][j];
    }

    MST t(m, n);
    t.Kruskal();
    return 0;
}