最小权顶点覆盖问题.cpp

最小权定点覆盖问题的C++代码

// 最小权顶点覆盖问题

#include <iostream>

using namespace std;
 
template <class T>
class MinHeap{
public:
    MinHeap(int MinHeapSize=10000);
    ~MinHeap() { delete []heap; }
    int Size() const{ return last; }
    MinHeap<T>& Insert(const T& x);
    MinHeap<T>& DeleteMin(T& x);
private:
    int last, MaxSize;
    T* heap;
};

template<class T>
MinHeap<T>::MinHeap(int MinHeapSize) {
    MaxSize = MinHeapSize;
    heap = new T[MaxSize+1];
    last = 0;
}

template<class T>
MinHeap<T>& MinHeap<T>::Insert(const T& x) {
    int i = ++last;
    while(i != 1 && x < heap[i/2]) {
        heap[i] = heap[i/2];
        i /= 2;
    }
    heap[i] = x;
    
    return *this;
}

template<class T>
MinHeap<T>& MinHeap<T>::DeleteMin(T& x){
    x = heap[1];
    T y = heap[last--];
    int i = 1,ci = 2;
    while(ci <= last){
       if(ci<last && heap[ci+1]<heap[ci])
           ci++;
       if(y < heap[ci])
           break;
       heap[i] = heap[ci];
       i = ci;
       ci *= 2;
    }
    heap[i] = y;
    return *this;
}

class HeapNode
{
    friend class VertexCover;

public:
    operator int() const { return cn; }

private:
    int i, cn;
    char *x, *c;
};

class VertexCover
{
    friend int MinCover(int**, int[], int);

private:
    void search();
    bool cover(HeapNode E);
    void AddLiveNode(MinHeap<HeapNode> &H, HeapNode E, int cn, int i, bool ch);
    int **a, n, *w, *bestx, bestn;
};

void VertexCover::search()
{
    int j;
    MinHeap<HeapNode> H(10000);
    HeapNode E;
    E.x = new char[n+1];
    E.c = new char[n+1];
    for(j = 1; j <= n; ++j) {
        E.x[j] = E.c[j] = 0;
    }
    int i = 1, cn = 0;
    while(1) {
        if(i > n) {
            if(cover(E)) {
                for(j = 1; j <= n; ++j)
                    bestx[j] = E.x[j];
                bestn = cn;
                break;
            }
        } else {
            if(!cover(E))
                AddLiveNode(H, E, cn, i, 1);
            AddLiveNode(H, E, cn, i, 0);
        }
        if(H.Size() == 0)
            break;

       // 将舍弃结点的存储空间收回
       delete []E.x;
       delete []E.c;

        H.DeleteMin(E);
        cn = E.cn;
        i = E.i+1;
    }
}

bool VertexCover::cover(HeapNode E)
{
    for(int j = 1; j <= n; ++j)
        if( E.x[j] == 0 && E.c[j] == 0 )
            return false;
    return true;
}

void VertexCover::AddLiveNode(MinHeap<HeapNode> &H, HeapNode E, int cn, int i, bool ch)
{
    int j;
    HeapNode N;
    N.x = new char[n+1];
    N.c = new char[n+1];
    for(j = 1; j <= n; ++j) {
        N.x[j] = E.x[j];
        N.c[j] = E.c[j];
    }
    N.x[i] = ch;
    if(ch) {
        N.cn = cn + w[i];
        for(j = 1; j <= n; ++j)
            if(a[i][j])
                N.c[j]++;
    } else
        N.cn = cn;
    N.i = i;
    H.Insert(N);
}

int MinCover(int** a, int v[], int n)
{
    VertexCover Y;
    Y.w = new int[n+1];
    for(int j = 1; j <= n; ++j)
        Y.w[j] = v[j];
    Y.a = a;
    Y.n = n;
    Y.bestx = v;
    Y.search();
    return Y.bestn;
}

int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
    int n, e, u, v, i, j;
    int* p;
    int** a;
    
    cin >> n >> e;
    a = new int*[n+1];
    for(i = 0; i <= n; ++i)
        a[i] = new int[n+1];
    for(i = 0; i <= n; ++i)
        for(j = 0; j <= n; ++j)
            a[i][j] = 0;
    p = new int[n+1];
    for(i = 1; i <= n; ++i)
        cin >> p[i];
    for(i = 1; i <= e; ++i) {
        cin >> u >> v;
        a[u][v] = a[v][u] = 1;
    }
    cout << MinCover(a, p, n) << endl;
    for(i = 1; i <= n; ++i)
        cout << p[i] << " ";
    cout << endl;
    //system("pause");
    return 0;
}