题目描述
某个局域网内有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)最大,请求出这个最大值。
思路
这题一看就知道是最小生成树,将全部的边权加起来以后减去最小生成树的值就是答案
#include <stdio.h>
#include <algorithm>
using namespace std;
int f[1001];
struct arr
{
int x,y,z;
};
arr a[1001];
int cam(arr x,arr y)
{
return x.z<y.z;
}
int find(int x)
{
if (!f[x]) return x;
f[x]=find(f[x]);
return f[x];
}
int insert(int x,int y)
{
if (find(x)!=find(y))
{
f[find(x)]=find(y);
return 1;
}
return 0;
}
int main()
{
int n,m;
long long l=0;
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
l+=a[i].z;
}
sort(a+1,a+m+1,cam);
long long tot=0;
for (int i=1;i<=m;i++)
{
if (find(a[i].x)!=find(a[i].y))
{
tot+=a[i].z;
insert(a[i].x,a[i].y);
}
}
printf("%lld\n",l-tot);
}
Comments NOTHING