洛谷 P2820 局域网 - 数据结构 - 盲人摸象

# 题目

某个局域网内有 $n(n \le 100)$ 台计算机，由于搭建局域网时工作人员的疏忽，现在局域网内的连接形成了回路，我们知道如果局域网形成回路那么数据将不停的在回路内传输，造成网络卡的现象。因为连接计算机的网线本身不同，所以有一些连线不是很畅通，我们用 $f(i,j)$ 表示 $i,j$ 之间连接的畅通程度， $f(i,j)$ 值越小表示 $i,j$ 之间连接越通畅， $f(i,j)$ 为 $0$ 表示 $i,j$ 之间无网线连接。

需要解决回路问题，我们将除去一些连线，使得网络中没有回路，并且被除去网线的 $\sum f(i,j)$ 最大，请求出这个最大值。

Input

第一行两个正整数 $n,k$ 。

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

Output

一个正整数， $\sum f(i,j)$ 的最大值。

Sample Input & Output

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

# 并查集

	#include<bits/stdc++.h>
	using namespace std;
	struct ll{
	int xx,yy,zz;// 结构体分别存储边的两端点，长度
	}a[100001];
	bool cmp(ll x,ll y)
	{
	return x.zz<y.zz;//sort 排序设置边长为关键字
	}
	int n,m,s,n1,f[100001],l1,r1;
	int find(int a)// 找父亲
	{
	if(f[a]==a)return a;
	f[a]=find(f[a]);
	return f[a];
	}
	int main()
	{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
	cin>>a[i].xx>>a[i].yy>>a[i].zz;
	s=s+a[i].zz;// 总长
	}
	sort(a+1,a+1+m,cmp);
	for(int i=1;i<=n;i++)
	f[i]=i;// 赋初值
	for(int i=1;i<=m;i++)
	{
	l1=find(a[i].xx);r1=find(a[i].yy);
	if(l1!=r1)// 如果没联通，则联通 a [i].xx 和 a [i].yy 的父亲节点
	{
	f[l1]=r1;
	s-=a[i].zz;n1++;
	}
	if(n1==n-1)break;//n-1 条就可以退出
	}
	cout<<s;
	return 0;
	}

# 题目

# 并查集

2022.7.19

2022.7.20