時(shí)間限制: 1000 ms ??? ??? 內(nèi)存限制: 65536 KB
提交數(shù): 5574 ??? 通過(guò)數(shù): 3460

在網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)中從網(wǎng)站色彩、結(jié)構(gòu)布局、欄目設(shè)置、關(guān)鍵詞群組等細(xì)微處著手，突出企業(yè)的產(chǎn)品/服務(wù)/品牌，幫助企業(yè)鎖定精準(zhǔn)用戶，提高在線咨詢和轉(zhuǎn)化，使成都網(wǎng)站營(yíng)銷成為有效果、有回報(bào)的無(wú)錫營(yíng)銷推廣。成都創(chuàng)新互聯(lián)專業(yè)成都網(wǎng)站建設(shè)10余年了，客戶滿意度97.8%，歡迎成都創(chuàng)新互聯(lián)客戶聯(lián)系?！绢}目描述】

某個(gè)局域網(wǎng)內(nèi)有n(n≤100)臺(tái)計(jì)算機(jī)，由于搭建局域網(wǎng)時(shí)工作人員的疏忽，現(xiàn)在局域網(wǎng)內(nèi)的連接形成了回路，我們知道如果局域網(wǎng)形成回路那么數(shù)據(jù)將不停的在回路內(nèi)傳輸，造成網(wǎng)絡(luò)卡的現(xiàn)象。因?yàn)檫B接計(jì)算機(jī)的網(wǎng)線本身不同，所以有一些連線不是很暢通，我們用f(i,j)表示i,j之間連接的暢通程度(f(i,j)≤1000)，f(i,j)值越小表示i,j之間連接越通暢，f(i,j)為0表示i,j之間無(wú)網(wǎng)線連接。現(xiàn)在我們需要解決回路問(wèn)題，我們將除去一些連線，使得網(wǎng)絡(luò)中沒(méi)有回路，并且被除去網(wǎng)線的Σf(i,j)大，請(qǐng)求出這個(gè)大值。

【輸入】

第一行兩個(gè)正整數(shù)n,kn,k

接下來(lái)的k行每行三個(gè)正整數(shù)i,j,m表示i,j兩臺(tái)計(jì)算機(jī)之間有網(wǎng)線聯(lián)通，通暢程度為m。

【輸出】

一個(gè)正整數(shù)，Σf(i,j)Σf(i,j)的大值。

【輸入樣例】

5 5
1 2 8
1 3 1
1 5 3
2 4 5
3 4 2

【輸出樣例】

8

解釋：若我們?cè)O(shè)沒(méi)有被減去的連線為x，減去的連線為Σf(i,j)，，總連線的數(shù)量為f(i,j)，

則x+Σf(i,j)=f(i,j)，要想讓?duì)瞗(i,j)大則x要最小，所以留下的連線為最小，所以要求最小生成樹(shù)，先記錄總邊權(quán)，在用總邊權(quán)減去最小生成樹(shù)，就是大的Σf(i,j)；

代碼：

#includeusing namespace std;
struct node{
	int id,from,dist;
	node(){
	}
	node(int f,int i,int d){
		from=f;id=i;dist=d;
	}
	friend bool operator<(node a,node b){
		return a.dist>b.dist;
	}
};
int n,e,g[107][107],cnt=0,ans=0,k;
bool flag[107];
priority_queuepque;
vectorprim(int sid){
	vectorresult;
	memset(flag,false,sizeof(flag));
	pque.push(node(-1,sid,0));
	while(result.size()>n>>k;
	int i,j,m;
	for(int i1=1;i1<=k;i1++){
		cin>>i>>j>>m;
		g[i][j]=g[j][i]=m;
		ans+=m;
	} 
	vectornodes=prim(1);
	for(int i=0;i
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
            

            當(dāng)前題目：c++一本通1391：局域網(wǎng)(net)-創(chuàng)新互聯(lián)            

            新聞來(lái)源：http://weahome.cn/article/ieood.html