首页 > 代码库 > 洛谷 P2820 局域网
洛谷 P2820 局域网
题目背景
某个局域网内有n(n<=100)台计算机，由于搭建局域网时工作人员的疏忽，现在局域网内的连接形成了回路，我们知道如果局域网形成回路那么数据将不停的在回路内传输，造成网络卡的现象。因为连接计算机的网线本身不同，所以有一些连线不是很畅通，我们用f(i,j)表示i,j之间连接的畅通程度，f(i,j)值越小表示i,j之间连接越通畅，f(i,j)为0表示i,j之间无网线连接。
题目描述
需要解决回路问题，我们将除去一些连线，使得网络中没有回路，并且被除去网线的Σf(i,j)最大，请求出这个最大值。
输入输出格式
输入格式：第一行两个正整数n k
接下来的k行每行三个正整数i j m表示i,j两台计算机之间有网线联通，通畅程度为m。
输出格式：一个正整数，Σf(i,j)的最大值
输入输出样例
输入样例#1：
5 51 2 81 3 11 5 32 4 53 4 2
输出样例#1：
8
说明
f(i,j)<=1000
1 #include<cstdio> 2 #include<algorithm> 3 #include<iostream> 4 using namespace std; 5 struct node 6 { 7 int x; 8 int y; 9 int v;10 }a[8001];11 int father[8001],total=0;12 int find(int x)13 {14 if(father[x]!=x) father[x]=find(father[x]);15 return father[x];16 }17 /*void unionn(int x,int y)18 {19 int fa=find(x);20 int fb=find(y);21 if(fa!=fb)father[fa]=fb;22 }*/23 bool cmp(const node &x,const node &y){24 return x.v<y.v;25 }26 int main()27 {28 int n,m=0,x,y,v;29 scanf("%d%d",&n,&m);30 for(int i=1;i<=m;i++)31 {32 scanf("%d%d%d",&x,&y,&v);33 if(v==0) continue;34 a[i].x=x;35 a[i].y=y;36 a[i].v=v;37 total+=v;38 }39 int k=0;40 for(int i=1;i<=n;i++)41 father[i]=i;42 sort(a+1,a+m+1,cmp);43 for(int i=1;i<=m;i++)44 {45 int fa=find(a[i].x),fb=find(a[i].y);46 if(fa!=fb)47 {48 total-=a[i].v;49 k++;50 father[fa]=fb;51 }52 if(k==n-1)break;53 }54 cout<<total;55 return 0;56 }
洛谷 P2820 局域网
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。