题意：
有N个区域需要建设水资源工程，可以自建水库解决缺水，也可以从已有水源的地区建立管道引水，给出自建水库的费用\(W_i\)和相互引水的费用\(P_{i,j}\)，求工程的最小花费。
思路**：
最小生成树的模板题，稠密图，可以用Prim算法。以引水的费用作为边权，找到自建费用最低的区域，以它为根，通过比较自建和引水的最小值\(lowcost_i=\min(G_{k,i},cost_i)\)来不断生成树。
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 300;
#define FIO ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define FILEREAD freopen("input.txt", "r", stdin);
int G[N][N], lowcost[N], cost[N];
bool used[N];
int prim(int vcount, int minv)
{
int sum = 0;
for (int i = 0; i < vcount; i++)
{
lowcost[i] = min(G[minv][i], cost[i]);
used[i] = false;
}
used[minv] = true;
for (int i = 1; i <= vcount - 1; i++)
{
int j = 0, mincost = INF;
for (int k = 0; k < vcount; k++)
if ((!used[k]) && (lowcost[k] < mincost))
{
mincost = lowcost[k];
j = k;
}
used[j] = true;
sum += mincost;
for (int k = 0; k < vcount; k++)
if (!used[k] && (min(cost[k], G[j][k]) < lowcost[k]))
lowcost[k] = min(cost[k], G[j][k]);
}
return sum;
}
int main()
{
#ifndef ONLINE_JUDGE
FILEREAD
#endif
FIO
int k;
cin >> k;
while(k--)
{
int n;
cin >> n;
int minv = 0;
for (int i = 0; i < n; ++i)
{
cin >> cost[i];
if (cost[minv] > cost[i])
minv = i;
}
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
cin >> G[i][j];
cout << prim(n, minv) + cost[minv] << endl;
}
return 0;
}