c++一本通1391:局域网(net)-创新互联

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 5574     通过数: 3460

在网站设计、成都网站建设中从网站色彩、结构布局、栏目设置、关键词群组等细微处着手,突出企业的产品/服务/品牌,帮助企业锁定精准用户,提高在线咨询和转化,使成都网站营销成为有效果、有回报的无锡营销推广。成都创新互联专业成都网站建设10余年了,客户满意度97.8%,欢迎成都创新互联客户联系。【题目描述】

某个局域网内有n(n≤100)台计算机,由于搭建局域网时工作人员的疏忽,现在局域网内的连接形成了回路,我们知道如果局域网形成回路那么数据将不停的在回路内传输,造成网络卡的现象。因为连接计算机的网线本身不同,所以有一些连线不是很畅通,我们用f(i,j)表示i,j之间连接的畅通程度(f(i,j)≤1000),f(i,j)值越小表示i,j之间连接越通畅,f(i,j)为0表示i,j之间无网线连接。现在我们需要解决回路问题,我们将除去一些连线,使得网络中没有回路,并且被除去网线的Σf(i,j)大,请求出这个大值。

【输入】

第一行两个正整数n,kn,k

接下来的k行每行三个正整数i,j,m表示i,j两台计算机之间有网线联通,通畅程度为m。

【输出】

一个正整数,Σf(i,j)Σf(i,j)的大值。

【输入样例】
5 5
1 2 8
1 3 1
1 5 3
2 4 5
3 4 2
【输出样例】
8

解释:若我们设没有被减去的连线为x,减去的连线为Σf(i,j),,总连线的数量为f(i,j),

则x+Σf(i,j)=f(i,j),要想让Σf(i,j)大则x要最小,所以留下的连线为最小,所以要求最小生成树,先记录总边权,在用总边权减去最小生成树,就是大的Σ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

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


当前文章:c++一本通1391:局域网(net)-创新互联
新闻来源:http://scyanting.com/article/ieood.html