AcWing 4294. 修建道路
原题链接
简单
作者:
no_one
,
2022-08-08 18:37:30
,
所有人可见
,
阅读 232
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100010, M = 100010;
int n, m;
struct r{
long long x, y, z;
bool operator < (const r &W) const
{
return z < W.z;
}
}edge[M];
long long q[N];
long long find(int i)
{
if(q[i] != i) q[i] = find(q[i]); // 找到祖宗节点。
return q[i]; // 返回祖宗节点。
}
int main()
{
while(cin >> n)
{
m = 0;
for(int i = 1; i <= n; i ++) q[i] = i;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
{
cin >> edge[++ m].z;
edge[m].x = i;
edge[m].y = j;
}
sort(edge + 1, edge + m + 1);
int k;
cin >> k;
for(int i = 0; i < k; i ++)
{
long long a, b;
cin >> a >> b;
q[find(a)] = find(b);
}
long long res = 0;
for(int i = 1; i <= m; i ++)
{
long long x = find(edge[i].x), y = find(edge[i].y);
if(x != y)
{
q[x] = y;
res += edge[i].z;
}
}
cout << res << endl;
}
return 0;
}