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