题解 洛谷P1546 [USACO3.1]最短网络 Agri-Net

题目描述
FJ 已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过 10^5。

巨水的最小生成树模板题，直接敲一个 prim 算法就行了。

code：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define inf 700000000
using namespace std;
int n,t[110],w[110][110],mst,bo[110],k;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
        cin>>w[i][j];
    memset(t,0x7f,sizeof(t));
    t[1]=0;
    for(int i=1;i<=n;i++)
    {
        k=0;
        for(int j=1;j<=n;j++)
          if(!bo[j]&&(t[j]<t[k]))
            k=j;
        bo[k]=1;
        for(int j=1;j<=n;j++)
          if(!bo[j]&&(w[k][j]<t[j]))
            t[j]=w[k][j];
    }
    for(int i=1;i<=n;i++)
      mst+=t[i];
    cout<<mst;
    return 0;
}

题解 洛谷P1546 [USACO3.1]最短网络 Agri-Net

原文：https://www.cnblogs.com/Akn-Wind/p/12660192.html