题解 P2126 【Mzc家中的男家丁】

fls233666 · 2019-08-18 01:55:53 · 题解

2020年2月16日更新：修正题解排版问题

不难看出，男家丁与 mzc 的通讯网络是一个图的结构。再根据通讯路线是双向的，我们就能得到第一个重要信息：题目给出了一个无向图。

接着，根据题目中要求把所有男家丁都叫到的最小总时间，可以得到第二个重要信息：题目要求一个图的最小生成树。

要求最小生成树，最重要的就是图一定要连通。对于图的连通性，题目中也给出了解释。题目保证能把每个人都叫到，就保证了图的连通性。

总结一下题意：

给出一张连通的无向图，求出这张图的最小生成树。

下面开始求解：

求解最小生成树，有两种办法(以下用 n 表示点数，用 m 表示边数)：

其中，Prim 还可以通过堆优化将时间复杂度优化到O(m \log(n))

分析此题的数据范围：n \le 2300,m \le 400000

显然，用无堆优化的 Prim 算法可以稳过。

Prim 的实现过程如下：

1. 初始化 dis 数组，将全部点赋值为无穷大，然后选择一个点把其 dis 值赋值为 0；
2. 选择一个没有处理过的，dis 值最小的点；
3. 把这个点标记为处理过，并用这个点连出去的边更新其它未处理的点的 dis 值；
4. 重复上述过程 n 次后，每个点都被处理过。这时把 dis 中的每个值加起来，就能得到最小生成树的边权和。

以下是代码：

#include<iostream>
#include<cstring>
#include<vector>
#define INF 2147000000   //无穷大
using namespace std;
int main(){
    int n,m,ans=0;
    cin>>n>>m;
    vector < pair<int,int> > vb[n+1];   //边链表存边
    for(int a,b,w,i=1;i<=m;i++){
        cin>>a>>b>>w;
        vb[a].push_back(make_pair(b,w));
        vb[b].push_back(make_pair(a,w));
        //无向边存两次
    }
  //数据读入与存储

    int dis[n+1];
    bool fw[n+1];   //标记每个点是否有被访问过
    for(int i=0;i<=n;i++)
        dis[i]=INF; 
    dis[0]=0;   //dis数组初始化赋值
    memset(fw,0,sizeof(fw));    //重置标记
    for(int mn=INF,u,tg=0;tg<n;tg++,mn=INF){
        for(int j=0;j<=n;j++){
            if(!fw[j]){
                if(mn>dis[j]){
                    mn=dis[j];
                    u=j;     
                } 
            }
        }
        //一个循环找到dis最小的未处理的点

        fw[u]=true;  //标记
        for(int lb=vb[u].size(),i=0;i<lb;i++)
            if(!fw[vb[u][i].first])    //更新未处理的点的dis值
                if(vb[u][i].second<dis[vb[u][i].first])
                    dis[vb[u][i].first]=vb[u][i].second;
    }
  //Prim运行过程

    for(int i=0;i<=n;i++)
        ans+=dis[i];    //累加求和并输出
    cout<<ans; 
    return 0;
}