xxxx18一60岁hd中国/日韩女同互慰一区二区/西西人体扒开双腿无遮挡/日韩欧美黄色一级片 - 色护士精品影院www

  • 大小: 363KB
    文件類型: .rar
    金幣: 2
    下載: 2 次
    發(fā)布日期: 2021-05-07
  • 語言: 其他
  • 標(biāo)簽:

資源簡介

★問題描述：給定一個賦權(quán)無向圖G=(V,E),每個頂點v∈V都有一個權(quán)值w(v)。如果U∈V,且對任意(u,v)∈E有u∈U或v∈U,就稱U為圖G的一個頂點條覆蓋.G的最小權(quán)頂點覆蓋是指G中所含頂點權(quán)之和最小的頂點覆蓋。 ★算法設(shè)計：對于結(jié)定的無向圖G,設(shè)計一個優(yōu)先隊列式分支限界法,計算G的最小權(quán)頂點覆蓋。 ★數(shù)據(jù)輸入：由文件input.txt給出輸入數(shù)據(jù)。第1行有2個正整數(shù)n和m,表示給定的圖G有n個頂點和m條邊,頂點編號為1,2,.....,n.第2行有n個正整數(shù)表示n個頂點的權(quán).接下來的m行中,每行有2 個正整數(shù)u,v,表示圖G的一條邊(u,v)。 ★結(jié)果輸出：將計算出的最小權(quán)頂點覆蓋的頂點權(quán)之和以及最優(yōu)輸出到文件output.txt.文件第1行是最小權(quán)頂點覆蓋頂點權(quán)之和;第2行是最優(yōu)解xi,1≤i≤n,xi=0表示頂點i不在最小權(quán)頂點覆蓋中。

資源截圖

代碼片段和文件信息 

#include?
#include“MinHeap.h“;
using?namespace?std;
?

//最小堆結(jié)點元素類型是HeapNode
class?HeapNode
{
????friend?class?VertexCover;

public:
????operator?int（）?const?{?return?cn;?}

private:
????int?i????//活結(jié)點所處的層序號
		cn???//當(dāng)前權(quán)植和
????????*x???//當(dāng)前解
		*c;???//指向活結(jié)點在子集樹中的結(jié)點的指針
};

//解最小權(quán)項點覆蓋問題的優(yōu)先隊列式分支界限法
class?VertexCover
{
????friend?int?MinCover（int**?int[]?int）;

private:
????void?search（）;
????bool?cover（HeapNode?E）;
????void?AddLiveNode（MinHeap?&H?HeapNode?E?int?cn?int?i?bool?ch）;
????int?**a??????????//圖的鄰接矩陣
		n????????????//圖的頂點數(shù)
		*w???????????//圖中每個頂點的權(quán)值
		*bestx??????//最優(yōu)解
		bestn;???????//當(dāng)前最小權(quán)值和
};

void?VertexCover::search（）
{
????int?j;
????MinHeap?H（1000）;?????//定義最小堆的容量為1000
????HeapNode?E;
????E.x?=?new?int[n+1];
????E.c?=?new?int[n+1];
????for（j?=?1;?j?<=?n;?j++）?
	{
????????E.x[j]?=?E.c[j]?=?0;
????}
????int?i?=?1?cn?=?0;??????//初始時擴(kuò)展結(jié)點在第一層，權(quán)值和為0
????while（1）?
	{
????????if（i?>?n）?
		{//到達(dá)葉結(jié)點
????????????if（cover（E））?
			{??//如果所有結(jié)點都覆蓋，得到一組頂點覆蓋，更新當(dāng)前最優(yōu)值和相應(yīng)的當(dāng)前最優(yōu)解
????????????????for（j?=?1;?j?<=?n;?j++）
????????????????????bestx[j]?=?E.x[j];
????????????????bestn?=?cn;
????????????????break;
????????????}
????????}?
		else?
		{//非葉結(jié)點
????????????if（!cover（E））?//結(jié)點沒有全部覆蓋，則添加活結(jié)點
????????????????AddLiveNode（H?E?cn?i?1）;????//檢查左兒子結(jié)點
????????????AddLiveNode（H?E?cn?i?0）;????????//右兒子結(jié)點
????????}
????????if（H.Size（）?==?0）???//如果堆容量為0，則跳出循環(huán)
????????????break;

???????//?將舍棄結(jié)點的存儲空間收回
???????delete?[]E.x;
???????delete?[]E.c;

????????//取下一擴(kuò)展結(jié)點
????????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;
}

//將活結(jié)點加入堆中
void?VertexCover::AddLiveNode（MinHeap?&H?HeapNode?E?int?cn?int?i?bool?ch）
{
????int?j;
????HeapNode?N;???
????N.x?=?new?int[n+1];
????N.c?=?new?int[n+1];
????for（j?=?1;?j?<=?n;?j++）?
	{
????????N.x[j]?=?E.x[j];
????????N.c[j]?=?E.c[j];
????}
????//檢查左兒子結(jié)點
????N.x[i]=ch?1:0;
????if（ch）?
	{//可行結(jié)點
????????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）;??//插入到活結(jié)點隊列
}

//完成最小覆蓋計算
int?MinCover（int**?a?int?v[]?int?n）
{
????VertexCover?Y;
????Y.w?=?new?int[n+1];??????//記錄每個結(jié)點的權(quán)值
????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;
}

void?main（）
{

????int?n?e?u?v?i?j;
????int*?p;
????int**?a;
????
	cout<<“input.txt:“<????cin?>>?n?>>?e;?????????????//輸入頂點數(shù)和邊數(shù)
????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[

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????3722??2009-12-20?20:45??五、分支限界法\6-2.cpp

?????文件???????3367??2009-12-23?11:03??五、分支限界法\6-2.dsp

?????文件????????514??2009-12-23?11:04??五、分支限界法\6-2.dsw

?????文件??????41984??2009-12-23?11:04??五、分支限界法\6-2.ncb

?????文件??????48640??2009-12-23?11:04??五、分支限界法\6-2.opt

?????文件????????733??2009-12-23?11:03??五、分支限界法\6-2.plg

?????文件?????548928??2009-12-23?11:03??五、分支限界法\Debug\6-2.exe

?????文件?????257300??2009-12-23?11:03??五、分支限界法\Debug\6-2.obj

?????文件????1098752??2009-12-23?11:03??五、分支限界法\Debug\6-2.pdb

?????文件?????118784??2009-12-23?11:03??五、分支限界法\Debug\vc60.pdb

?????文件???????1619??2009-12-20?20:02??五、分支限界法\MinHeap.h

?????目錄??????????0??2010-07-14?14:07??五、分支限界法\Debug

?????目錄??????????0??2009-12-23?11:04??五、分支限界法

-----------?---------??----------?-----??----

??????????????2124343????????????????????13


評論

共有 條評論