局域网
题目描述
核心思路
题意：给定一张有 n n n个点， k k k条边的无向有环图，要求删掉其中部分边，且不改变图的连通性的情况下，使得最终的图仍然是连通的不存在环，并且删除的边权之和最大，输出最大的所删边边权权和。从题意我们可以发现：
删边权和最大 ⟹ \implies ⟹ 剩下边权和最小 ⟹ \implies ⟹ 求最小生成树
但是题中并没有说图一定连通，这让这道题恶心了很多。也就是说，图中可能存在多棵树，这些树并不在同一个连通块中。假设有 A 1 A_1 A1， A 2 A_2 A2， A 3 A_3 A3这三颗树，它们都是独立的连通块，那么我们需要求出每树的最小生成树，不妨设为 x 1 , x 2 , x 3 x_1,x_2,x_3 x1,x2,x3，设这三棵树边权总和为 s u m sum sum，那么最终删除的边权之和最大为 s u m − ( x 1 + x 2 + x 3 ) sum-(x_1+x_2+x_3) sum−(x1+x2+x3)。
说到连通块，我们很容易想到Kruskal算法，它也是利用连通块思想来求解最小生成树。因此，这题我们可以采用Kruskal算法来求解，对于一棵树来说，如果两个点不在同一个集合中，则说明它是最小生成树中的边，那么就可以累加边权。如果两个点已经在一个集合中了，根据Kruskal算法思想，则不需要累加边权了。
当然这题也是可以用prim算法的。
下面给出一个有多棵树的栗子：
如图所示：
将所有边权从小到大排好序，初始化每个节点都是独立集合（独立的连通块），设 a n s = 0 ans=0 ans=0
- 对于树 A A A，节点 1 1 1和节点 2 2 2起初都是独立的集合，那么可以使用并查集进行合并，因此需要累加边权，即 a n s + = w ans+=w ans+=w，也就是 a n s = 0 + 10 = 10 ans=0+10=10 ans=0+10=10，此时树 A A A就已经是一个连通块了
- 对于树 B B B，由于 ( 3 , 4 ) (3,4) (3,4)边权小，所有选择这条边，节点 3 , 4 3,4 3,4起初都是独立的集合，那么可以使用并查集进行合并，更新节点 4 4 4的祖宗节点为 3 3 3，因此需要累加边权，即 a n s + = w ans+=w ans+=w，也就是 a n s = 10 + 11 = 21 ans=10+11=21 ans=10+11=21，此时节点 3 3 3和节点 4 4 4就属于同一个连通块了。接着由于 ( 4 , 5 ) (4,5) (4,5)边权小，所以选择这条边，经过上一步的操作后，此时 ( 3 , 4 ) (3,4) (3,4)属于一个连通块，而 5 5 5是独立的一个集合，因此 5 5 5属于另一个连通块，那么可以使用并查集进行合并，更新节点 5 5 5的祖宗节点为 3 3 3，因此需要累加边权，即 a n s + = w ans+=w ans+=w，也就是 a n s = 21 + 12 = 33 ans=21+12=33 ans=21+12=33，此时 ( 3 , 4 , 5 ) (3,4,5) (3,4,5)已经在同一个连通块中了。最后选择 ( 3 , 5 ) (3,5) (3,5)这条边，但是由于 ( 3 , 4 , 5 ) (3,4,5) (3,4,5)已经在同一个连通块中了，所以此时 ( 3 , 5 ) (3,5) (3,5)这条边并不需要累加权值。也就是说 ( 3 , 5 ) (3,5) (3,5)这条边并不是最小生成树上的边。所以 a n s ans ans仍为 33 33 33，树 B B B的最小生成树的边有 ( 3 , 4 ) (3,4) (3,4)和 ( 4 , 5 ) (4,5) (4,5)
- 对于树 C C C，由于 ( 7 , 6 ) (7,6) (7,6)边权小，所以选择这条边，节点 7 , 6 7,6 7,6起初都是独立的集合，那么可以使用并查集进行合并，更新节点 7 7 7的祖宗节点为 6 6 6，因此需要累加边权，即 a n s + = w ans+=w ans+=w，也就是 a n s = 33 + 14 = 47 ans=33+14=47 ans=33+14=47，那么此时节点 7 7 7和节点 6 6 6就已经在同一个连通块中了。接着考虑 ( 6 , 7 ) (6,7) (6,7)这条边，由于 ( 6 , 7 ) (6,7) (6,7)已经在同一个连通块中了，所以这条边并不需要累加权值。也就是说 ( 6 , 7 ) (6,7) (6,7)这条边并不是最小生成树上的边。所以 a n s ans ans仍为 47 47 47，树 C C C的最小生成树的边有 ( 7 , 6 ) (7,6) (7,6)
- 由于这三颗树的边权总和为 s u m = 75 sum=75 sum=75，而我们已经求出了这三棵树的最小生成树之和为 47 47 47，那么需要删除的边的最大权值为 s u m − r e s = 75 − 47 = 28 sum-res=75-47=28 sum−res=75−47=28，也就是图中的红色边
代码
写法1：Kruskal算法
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110,M=210,INF=0x3f3f3f3f;
int n,m;
struct Edge{
int a,b,w;
bool operator < (const Edge& W)const{
return w<W.w;
}
}edges[M];
int p[N];
int find(int x)
{
if(x!=p[x])
p[x]=find(p[x]);
return p[x];
}
int Kruskal()
{
sort(edges,edges+m); //将边权从小到大排序
for(int i=1;i<=n;i++) //初始化每个点都是独立的集合
p[i]=i;
int res=0; //最小生成树的权值
//由于边已经排好序了 所以这里是优先选择小的边
//要注意这些边并不都是连通的 (存在多个非连通块)
for(int i=0;i<m;i++)
{
int a=find(edges[i].a);
int b=find(edges[i].b);
int w=edges[i].w;
//对于每个连通块来说,我们都只会在当两个节点的集合号不同时 才累加权值
//因为Kruskal算法就是当合并两个集合时,才累加了边权,而如果已经在同一个连通块中了,那么就不会累加
if(a!=b)
{
p[a]=b;
//只有不在同一集合时,才累加权值
res+=w;
}
}
//返回最小生成树的权值
return res;
}
int main()
{
int sum=0;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
edges[i]={a,b,w};
//计算全部边权的总和
sum+=w;
}
int t=Kruskal();
//总和减去最小生成树,那么剩下的其实就是被除去网线的最大值
printf("%d\n",sum-t);
return 0;
}
写法2：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110,INF=0x3f3f3f3f;
//prim算法需要用到邻接矩阵
int g[N][N];
int n,k;
//dist[i]表示节点i到集合S的距离
int dist[N];
//st[i]=true表示节点i已经被加入了集合S中
bool st[N];
//prim算法求解最小生成树
int prim()
{
int res=0;
memset(dist,0x3f,sizeof dist);
for(int i=0;i<n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
if(!st[j]&&(t==-1||dist[t]>dist[j]))
t=j;
if(i&&dist[t]==INF)
continue;
if(i)
res+=dist[t];
st[t]=true;
for(int k=1;k<=n;k++)
dist[k]=min(dist[k],g[t][k]);
}
return res;
}
int main()
{
memset(g,0x3f,sizeof g); //初始化邻接矩阵为正无穷
scanf("%d%d",&n,&k);
int total; //记录输入的所有子树的权值总和
while(k--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
//防止重边和自环
g[a][b]=g[b][a]=min(g[a][b],c);
//算出整个森林的边权总和
total+=c;
}
//由于题目给定的树不一定都是连通的,也就是说可能存在多个互不连通的树,即存在多个连通块
//依次求解每颗树中的最小生成树
for(int i=1;i<=n;i++)
{
//如果还没有处理节点i所在的树,则去求解i所在的这颗树的最小生成树
if(!st[i])
total-=prim(); //用总和减去每一颗树的最小生成树
}
printf("%d\n",total);
return 0;
}