题目描述
某个局域网内有 n 台计算机和 k 条 双向 网线,计算机的编号是 1∼n 。由于搭建局域网时工作人员的疏忽,现在局域网内的连接形成了回路,我们知道如果局域网形成回路那么数据将不停的在回路内传输,造成网络卡的现象。
注意:
对于某一个连接,虽然它是双向的,但我们不将其当做回路。本题中所描述的回路至少要包含两条不同的连接。
两台计算机之间最多只会存在一条连接。
不存在一条连接,它所连接的两端是同一台计算机。
因为连接计算机的网线本身不同,所以有一些连线不是很畅通,我们用 f(i,j) 表示 i,j 之间连接的畅通程度, f(i,j) 值越小表示 i,j 之间连接越通畅。
现在我们需要解决回路问题,我们将除去一些连线,使得网络中没有回路且不影响连通性(即如果之前某两个点是连通的,去完之后也必须是连通的),并且被除去网线的 Σf(i,j) 最大,请求出这个最大值。
输入格式
第一行两个正整数 n,k 。
接下来的 k 行每行三个正整数 i,j,m 表示 i,j 两台计算机之间有网线联通,通畅程度为 m 。
输出格式
一个正整数,表示被除去网线的 Σf(i,j) 的最大值。
数据范围
1≤n≤100
0≤k≤200
1≤f(i,j)≤1000
样例
输入样例:
5 5
1 2 8
1 3 1
1 5 3
2 4 5
3 4 2
输出样例:
8
算法1
(最小生成树)
题目大致意思就是删掉一些边使得身下的点两两联通,且删去边权总会最大
剩下最小,那不就是求最小生成树的问题了吗;
so kruskal 一波!!!
C++ 代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100000;
const int inf = 0x7fffffff;
struct node{
int a;
int b;
int val;
bool operator < (const node &x) const // 重载“<”
{
return x.val>val;
}
}e[N << 1];
int n,m,fa[N << 1];
int sum;
int find(int x) //并查集-状态压缩
{
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int read() //快读
{
char c = getchar();
int f = 1, x = 0;
while(!isdigit(c)) {if(c == '-') f = -1;c = getchar();}
while(isdigit(c)){x = x * 10 + c - 48;c = getchar();}
return x * f;
}
int ans,cnt;
void kru() //kruskal求最小生成树
{
sort(e+1,e+m+1);
for(int i=1;i<=m;i++)
{
int x,y;
x = find(e[i].a);
y = find(e[i].b);
if(x == y) continue;
fa[x]=y;
ans+=e[i].val; //将最小生成树中的每一个边的边权加起来
cnt++;
if(cnt>=n-1) break;
}
}
int main()
{
n = read(),m = read();
for(int i=1;i<=m;i++)
{
e[i].a = read();
e[i].b = read();
e[i].val = read();
sum+=e[i].val; //讲所有边的边权全加起来
}
for(int i=1;i<=n;i++) fa[i]=i;//并查集基本操作
kru();
printf("%d",sum-ans); //最大减最小,那不就是差值最大化吗!
return 0;
}
重载运算符为什么要把 < 重载成 > 啊,难道不是从小到大排吗