新的开始

多起点多终点最短路 最小生成树 T3 信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn) 发展采矿业当然首先得有矿井，小 FF 花了上次探险获得的千分之一的财富请人在岛上挖了 $n$ 口矿井，但他似乎忘记考虑的矿井供电问题……

为了保证电力的供应，小 FF 想到了两种办法：

在这一口矿井上建立一个发电站，费用为 $v$（发电站的输出功率可以供给任意多个矿井）。

将这口矿井与另外的已经有电力供应的矿井之间建立电网，费用为 $p$。

小 FF 希望身为「NewBe_One」计划首席工程师的你帮他想出一个保证所有矿井电力供应的最小花费。

输入

第一行一个整数 $n$，表示矿井总数。

第 $2\sim n+1$ 行，每行一个整数，第 $i$ 个数 $v_i$ 表示在第 $i$ 口矿井上建立发电站的费用。

接下来为一个 $n\times n$ 的矩阵 $p$，其中 $p_i,j$ 表示在第 $i$ 口矿井和第 $j$ 口矿井之间建立电网的费用（数据保证有$p_i,j=p_j,i$ ，且 $p_i,i=0$。

输出

输出仅一个整数，表示让所有矿井获得充足电能的最小花费。

输入样例

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

输出样例

9

提示

样例解释

小 FF 可以选择在 4 号矿井建立发电站然后把所有矿井都不其建立电网，总花费是 3+2+2+2=9。

数据范围:

对于 $30\%$ 的数据：$1\le n\le 50$；

对于 $100\%$ 的数据：$1\le n\le 300,0\le v_i,p_i,j\le 10^5$​​ 。

思路

给一个无向图, 两个矿井可以相连当且仅当有一方有电力, 求连通所有矿井的最小花费。

任选一个点A建立发电站, 然后让所有矿井与该点相连, 可以看做是从A点为起点的最小生成树。而最优结果需要考虑其他矿井为起点的情况。

可以枚举每一个矿井为起点的情况么？显然不行, 最优结果可能不止放一个发电站, 若状态压缩枚举所有放置情况, 状态数又太多。

回忆一下单源最短路的问题, 有个应对多起点的技巧, 建立虚拟源点。这里就创建一个虚拟源点, 和其他所有点链接, 权值为建发电站的费用。接着从该源点求最小生成树即可。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 3e2 + 10;
int n, m;
int g[N][N];
int dist[N];
bool st[N];
 
int prim()
{
    memset(dist, 0x3f, sizeof dist);
    dist[0] = 0;
    int res = 0;
    for (int i = 0; i < n + 1; i++)
    {
        int t = -1;
        for (int j = 0; j <= n; j++)
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
 
        st[t] = true;
        res += dist[t];
 
        for (int j = 0; j <= n; j++)
            dist[j] = min(dist[j], g[t][j]);
    }
 
    return res;
}
 
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int t;
        cin >> t;
        g[0][i] = t;
    }
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> g[i][j];
 
    cout << prim();
 
    return 0;
}