//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