uprim.cpp

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

#include <fstream>

using namespace std;

ofstream cout("out.txt");
ifstream cin("in.txt");
//---------------------------------------------------------------------------
class MST
{
    int **M, **E;
    int n;
    int *N;
    int Prim();
public:
    MST(int **m, int num);
    ~MST();
    void Print();
};

MST::MST(int **m, int num): M(m), n(num)
{
    E = new int*[n - 1];
    for (int i = 0; i < n - 1; i++)
        E[i] = new int[2];
    N = new int[n];
    for (int i = 0; i < n; i++) N[i] = 0;
}

MST::~MST()
{
    for (int i = 0; i < n - 1; i++)
        delete [] E[i];
    delete [] E;
    delete [] N;
}

void MST::Print()
{
    int mincost = Prim();
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cout << M[i][j] << "\t";
        cout << endl;
    }
    cout << endl;
    for (int i = 0; i < n - 1; i++)
        cout << char('a' + E[i][0]) << "\t"
             << char('a' + E[i][1]) << "\t"
             << M[E[i][0]][E[i][1]] << endl;
    cout << "\t\t" << mincost << endl;
}

int MST::Prim()
{
    int mincost = 0;
    N[0] = -1;
    for (int i = 1; i < n; i++)
    {
        int j = 0, cost = 0x7fffffff;
        for (int k = 1; k < n; k++)
            if (N[k] >= 0 && M[N[k]][k] < cost)
            {
                cost = M[N[k]][k];
                j = k;
            }
        mincost += cost;
        E[i - 1][0] = N[j]; E[i - 1][1] = j;
        N[j] = -1;
        for (int k = 1; k < n; k++)
            if (N[k] >= 0 && M[N[k]][k] > M[j][k])
                N[k] = j;
    }
    return mincost;
}

int main()
{
    int n, **M;
    cin >> n;
    M = new int*[n];
    for (int i = 0; i < n; i++)
    {
        M[i] = new int[n];
        M[i][i] = 0;
    }
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
        {
            cin >> M[i][j];
            M[j][i] = M[i][j];
        }
    MST mst(M, n);
    mst.Print();
    
    return 0;
}