最小权顶点覆盖问题

项目设计：最小权顶点覆盖问题 给定一个赋权无向图 G=(V,E)，每个顶点 v V ∈ 都有一个权值 w(v)。如果 U 包含于 V， 且对于 ， 且对于(u,v) E ∈ 有 u U ∈ 且 v V ∈ -U，则有 v K. ∈ 如：U = {1}, 若有边（1，2） ， 则有 2 属 于 属 于 K. 若有集合 U 包含于 V 使得 U + K = V, 就称 U 为图 G 的一个顶点覆盖。 G 的最小权 顶点覆盖是指 的最小权 顶点覆盖是指 G 中所含顶点权之和最小的顶点覆盖

//MinCover.cpp

#include
#include

#include“MinHeap.h“

int *p;

//最小堆结点
class HeapNode
{
friend class VC;
public:
operator int（）const{return cn;}
private:
   int icn*x*c;
};

class VC
{
friend MinCover（int **int []int）;
private:
void BBVC（）;
bool cover（HeapNode E）;
void AddLiveNode（MinHeap&HHeapNode Eint cnint ibool ch）;
int **an*w*bestxbestn;
};

void VC::BBVC（）
{
MinHeapH（100000）;
HeapNode E;
E.x=new int[n+1];
E.c=new int[n+1];
for（int j=1;j<=n;j++）
{
   E.x[j]=E.c[j]=0;
}

int i=1cn=0;
while（true）
{
   if（i>n）
   {
    if（cover（E））
    {
     for（int j=1;j<=n;j++）
      bestx[j]=E.x[j];
     bestn=cn;
     break;
    }
   }
   else
   {
    if（!cover（E））
     AddLiveNode（HEcnitrue）;
    AddLiveNode（HEcnifalse）;
   }

   if（H.IsEmpty（））break;
   H.RemoveMin（E）;
   cn=E.cn;
   i=E.i+1;
}
}

//cover

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

void VC::AddLiveNode（MinHeap &HHeapNode Eint cnint ibool ch）
{
HeapNode N;
N.x=new int[n+1];
N.c=new int[n+1];
for（int j=1;j<=n;j++）
{
   N.x[j]=E.x[j];
   N.c[j]=E.c[j];
}
N.x[i]=ch?1:0;
if（ch）
{
   N.cn=cn+w[i];
   for（int j=1;j<=n;j++）
    if（a[i][j]>0）
     N.c[j]++;
}
else 
{
   N.cn=cn;
}
N.i=i;
H.Insert（N）;
}

int MinCover（int **aint v[]int n）
{
VC 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.BBVC（）;
return Y.bestn;
}

int main（）
{
int uv;
int nc;
ifstream infile（“input.txt“）;
if（!infile）
{
   cout<<“Can‘t open input.txt“<   return 0;
}
ofstream outfile（“output.txt“）;
if（!outfile）
{
   cout<<“Can‘t open output.txt“<   return 0;
}

infile>>n>>c;
//Make2DArray（an+1n+1）;
int **a;
a=new int *[n+1];
for（int k=0;k<=n;k++）
   a[k]=new int[n+1];
for（int i=0;i<=n;i++）
   for（int j=0;j<=n;j++）
    a[i][i]=0;
p=new int[n+1];
for（i=1;i<=n;i++）
   infile>>p[i];
for（i=1;i<=c;i++）
{
   infile>>u>>v;
   a[u][v]=1;
   a[v][u]=1;
}
cout<for（i=1;i<=n;i++）
   cout<cout<return 0;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2013-05-09 11:06  最小权顶点覆盖问题\
     文件        2268  2009-12-24 08:46  最小权顶点覆盖问题\6_2.cpp
     文件        3365  2011-12-29 19:18  最小权顶点覆盖问题\6_2.dsp
     文件         531  2011-12-29 19:46  最小权顶点覆盖问题\6_2.dsw
     文件       33792  2011-12-29 19:46  最小权顶点覆盖问题\6_2.ncb
     文件       48640  2011-12-29 19:46  最小权顶点覆盖问题\6_2.opt
     文件         677  2011-12-29 19:35  最小权顶点覆盖问题\6_2.plg
     目录           0  2013-05-09 11:06  最小权顶点覆盖问题\Debug\
     文件      209018  2011-12-29 19:35  最小权顶点覆盖问题\Debug\6_2.exe
     文件      259344  2011-12-29 19:35  最小权顶点覆盖问题\Debug\6_2.ilk
     文件       22889  2011-12-29 19:35  最小权顶点覆盖问题\Debug\6_2.obj
     文件      297148  2011-12-29 19:18  最小权顶点覆盖问题\Debug\6_2.pch
     文件      443392  2011-12-29 19:18  最小权顶点覆盖问题\Debug\6_2.pdb
     文件       41984  2011-12-29 19:35  最小权顶点覆盖问题\Debug\vc60.idb
     文件       69632  2011-12-29 19:18  最小权顶点覆盖问题\Debug\vc60.pdb
     文件        2498  2009-12-24 08:44  最小权顶点覆盖问题\MinHeap.h
     文件          65  2013-05-09 11:15  最小权顶点覆盖问题\input.txt
     文件           0  2011-12-29 19:35  最小权顶点覆盖问题\output.txt