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

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

某个局域网内有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://cqcxhl.cn/article/ieood.html