ACM模版
描述
题解
这个题用最小生成树的两个经典算法都可以过，用 Prim 算法相对容易写，只要再不断扩展的过程中判定究竟是建站消耗高还是建管道高，如果用 Kruskal 算法的话，则需要在生成最小树的过程中存树，然后 dfs 一遍做和前者同样的判定即可。
我用的是第二种，但是其实 Kruskal 算法还有更简单的解法，只消建一个超级源点即可，将所有站的建站消费都转化为边权连在超级源点上即可。
代码
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;
const int INF =
0x3f3f3f3f;
const int MAXN =
333;
const int MAXM =
1e5;
int map[MAXN][MAXN];
vector<int> tree[MAXN];
int F[MAXN];
struct Edge
{
int u;
int v;
int w;
} edge[MAXM];
int tol;
int vis[MAXN];
void init()
{
tol =
0;
for (
int i =
0; i < MAXN; i++)
{
tree[i].clear();
}
memset(vis,
0,
sizeof(vis));
}
void addEdge(
int u,
int v,
int w)
{
edge[tol].u = u;
edge[tol].v = v;
edge[tol++].w = w;
}
bool cmp(Edge a, Edge b)
{
return a.w < b.w;
}
int find(
int x)
{
if (F[x] == x)
{
return x;
}
else
{
return F[x] = find(F[x]);
}
}
int Kruskal(
int n)
{
for (
int i =
0; i <= n; i++)
{
F[i] = i;
}
sort(edge, edge + tol, cmp);
int cnt =
0;
int ans =
0;
for (
int i =
0; i < tol; i++)
{
int u = edge[i].u;
int v = edge[i].v;
int w = edge[i].w;
int tOne = find(u);
int tTwo = find(v);
if (tOne != tTwo)
{
ans += w;
F[tOne] = tTwo;
cnt++;
tree[u].push_back(v);
tree[v].push_back(u);
}
if (cnt == n -
1)
{
break;
}
}
if (cnt < n -
1)
{
return -
1;
}
else
{
return ans;
}
}
int ans;
int value[MAXN];
void dfs(
int root)
{
for (
int i =
0; i < tree[root].size(); i++)
{
int tmp = tree[root][i];
if (!vis[tmp])
{
vis[tmp] =
1;
if (value[tmp] <
map[root][tmp])
{
ans += value[tmp] -
map[root][tmp];
}
dfs(tmp);
}
}
}
int main()
{
int K;
cin >> K;
int N;
while (K--)
{
init();
cin >> N;
int minValue = INF;
int root = -
1;
for (
int i =
0; i < N; i++)
{
cin >> value[i];
if (value[i] < minValue)
{
minValue = value[i];
root = i;
}
}
vis[root] =
1;
for (
int i =
0; i < N; i++)
{
for (
int j =
0; j < N; j++)
{
cin >>
map[i][j];
if (i != j)
{
addEdge(i, j,
map[i][j]);
}
}
}
ans = Kruskal(N);
ans += minValue;
dfs(root);
cout << ans <<
'\n';
}
return 0;
}
