本文共 3264 字，大约阅读时间需要 10 分钟。

Prim / Kruskal - 局域网 - 洛谷 P2820

某个局域网内有 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\le n\le 100，0\le k\le 200，1\le f(i,j)\le 1000$

输入样例：

5 51 2 81 3 11 5 32 4 53 4 2

输出样例：

8

分析：

$根据题意：给定一个包含多个连通块的图，要从每个连通块中去除几条边。$

$要求：去除几条边后，每个连通块中的点的数量不变，换言之，不改变任何两点之间的连通性。$

$要求去除掉的所有边的权值之和的最大值。$

$等价于求，将所有连通块变成最小生成树后，需要去掉的边的权值之和。$

$解决方案：$

$①、Prim算法：逐个向集合中添加到连通块距离最短的点，直到剩下的点与当前连通块不连通。$

$当剩下的点都不连通时，会默认选择一个未被标记过的点t，接着更新与t相邻的点的距离，计算新的连通块。$

$这样，我们先累加输入的所有边的权值总和tot，再对所有连通块求最小生成树，代价res，输出tot-res。$

$注意，只有当连通的时候我们才累加到各连通块最小生成树的总代价中，即dis[j]\ne inf时，才累加。$

$②、Kruskal算法：方便用于处理多个连通块的最小生成树。$

$但是注意，要求去除的边的权值之和，故我们要累加被舍弃掉的边的权值。$

代码：

Prim算法：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int N=110, inf=0x3f3f3f3f;int n,m,g[N][N],dis[N];bool st[N];int prim(){       memset(dis,0x3f,sizeof dis);    dis[1]=0;        int res=0;    for(int i=0;i
       
        dis[j]))                t=j;                        if(dis[t]!=inf) res+=dis[t];        st[t]=true;                for(int j=1;j<=n;j++) dis[j]=min(dis[j],g[t][j]);    }        return res;}int main(){       scanf("%d%d",&n,&m);        memset(g,0x3f,sizeof g);    int a,b,c,tot=0;    for(int i=0;i
       
      
     
    
   

Kruskal算法：

#include
   
    #include
    
     #include
     
      using namespace std;const int N=210;int n,m;int p[N];struct edge{       int u,v,w;    bool operator < (const edge &t) const    {           return w
      
       >n>>m;    for(int i=0;i
       
        >E[i].u>>E[i].v>>E[i].w;    for(int i=1;i<=n;i++) p[i]=i;        int res=kruskal();        cout<
        
         <