我知道为什么了,今天上午不太清醒,比如135相连,如果3选择了挖井而不连,那么1和5就断了
by yanguo12138 @ 2024-04-21 18:35:13
这是我的ac代码,望各位大犇指点一下
```cpp
#include<iostream>
#include<math.h>
#include<map>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5 + 5;
int p[N];
struct node
{
int x, y, w;
bool operator<(const node& Z)const
{
return w < Z.w;
}
}e[N];
int find(int x)
{
if (p[x] != x)p[x] = find(p[x]);
return p[x];
}
int main()
{
int n;
cin >> n;
for (int i = 0; i <= n; i++)p[i] = i;
int wz[400][400] = { 0 };
int dj[400] = { 0 };
int o = 0;
for (int i = 0; i < n; i++)
{
cin >> dj[i];
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> wz[i][j];
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (wz[i][j] != 0)e[o].x = i, e[o].y = j, e[o].w = wz[i][j], o++;
}
}
for (int i = 0; i < n; i++)
{
e[o].x = n, e[o].y = i, e[o].w = dj[i];
o++;
}
sort(e, e + o);
int ans = 0;
for (int i = 0; i < o; i++)
{
int x = e[i].x, y = e[i].y, w = e[i].w;
int a = find(x), b = find(y);
if (a != b)
{
p[a] = b;
ans += w;
for (int i = 1; i <= n; i++)
{
p[i] = find(i);
}
}
}
cout << ans;
return 0;
}
```
by yanguo12138 @ 2024-04-21 18:49:41