資源簡介
項目設計:最小權頂點覆蓋問題
給定一個賦權無向圖 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
- 上一篇:OpenGL 火箭
- 下一篇:遺傳算法0-1背包問題論文
評論
共有 條評論