题目描述
某个局域网内有 n 台计算机和 k 条 双向 网线,计算机的编号是 1∼n。由于搭建局域网时工作人员的疏忽,现在局域网内的连接形成了回路,我们知道如果局域网形成回路那么数据将不停的在回路内传输,造成网络卡的现象。
注意:
对于某一个连接,虽然它是双向的,但我们不将其当做回路。本题中所描述的回路至少要包含两条不同的连接。
两台计算机之间最多只会存在一条连接。
不存在一条连接,它所连接的两端是同一台计算机。
因为连接计算机的网线本身不同,所以有一些连线不是很畅通,我们用 f(i,j) 表示 i,j 之间连接的畅通程度,f(i,j) 值越小表示 i,j 之间连接越通畅。
现在我们需要解决回路问题,我们将除去一些连线,使得网络中没有回路且不影响连通性(即如果之前某两个点是连通的,去完之后也必须是连通的),并且被除去网线的 Σf(i,j) 最大,请求出这个最大值。
算法1
(prim) $O(n^2)$
按照y总所说的prim算法要考虑到不同连通块的问题,但后来经过我自己瞎加了个条件后发现可以直接AC掉,真神奇!
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 110;
int w[N][N];
int dist[N];
bool st[N];
int n,m,sum;
int prim()
{
memset(dist,0x3f,sizeof dist);
dist[1] = 0;
int res = 0;
for(int i = 1 ; i <= n; i ++)
{
int t = -1;
for(int j = 1; j <= n ;j ++)
if(!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
st[t] = true;
if(dist[t] != 0x3f3f3f3f)res += dist[t];//这里多加一个判断条件就可以直接AC掉
for(int j = 1; j <= n ; j ++)
dist[j] = min(dist[j],w[t][j]);
}
return res;
}
int main()
{
cin>>n>>m;
memset(w,0x3f,sizeof w);
for(int i = 1; i <= m ; i ++)
{
int a,b,c;
cin>>a>>b>>c;
w[a][b] = w[b][a] = min(w[a][b],c);
sum += c;
}
cout<<sum - prim()<<endl;
return 0;
}
算法2
(kruskal) $O(nlogn)$
正宗做法
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 110, M = 210;
struct edge
{
int a,b,w;
bool operator < (const edge &t)const
{
return w < t.w;
}
}e[M];
int p[N];
int n,m;
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin>>n>>m;
for(int i = 0 ;i < n ; i ++)p[i] = i;
for(int i = 0 ; i < m ; i ++)
{
int a,b,w;
cin>>a>>b>>w;
e[i] = {a,b,w};
}
sort(e,e + m);
int res = 0;
for(int i = 0 ; i < m ;i ++)
{
int a = find(e[i].a),b = find(e[i].b),w = e[i].w;
if(a != b)p[a] = b;
else res += w;
}
cout<<res<<endl;
return 0;
}
prim那里不算乱加吧,就是累加最小生成树的边权。 %%%