下面是两份代码，唯一的不同就是

• 一个我是用vector排序维护的最小值
• 一个是直接用数组维护的最小值

但是vector的错了，后者对了，就因为这一个点，对着题解想了两个小时，真心请教各位大佬，教教我这个菜鸡

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){int x;scanf("%lld",&x);return x;}
const int B=1e6+10;
const int inf=0x3f3f3f3f;
int T;
int n;
int a[B];
vector<int>v[1000009];
int fa[B];
int find(int x)
{
	if (fa[x]==x) return x;
	else return fa[x]=find(fa[x]);
}
struct node
{
	int u,v,x;
}e[B];
int cmp(node a,node b)
{
	return a.x<b.x;
}
void work()
{
	n=read();
	int tot=0;
	for (int i=1;i<=n;i++) a[i]=read(),fa[i]=i;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++) 
		{
			int x=read();
			if (!a[i] || !a[j]) continue;
			e[++tot]={i,j,x};
			v[i].push_back(x);
		}
		sort(v[i].begin(),v[i].end());
	}
	int sum=0;
	sort(e+1,e+1+tot,cmp);
	for (int i=1;i<=tot;i++)
	{
		if (e[i].u==e[i].v) continue; 
		int u=find(e[i].u);
		int v=find(e[i].v);
		if (fa[u]==fa[v]) continue;
		fa[v]=u;
		sum+=e[i].x;
	}
	for (int i=1;i<=n;i++)
	{
		int res=a[i]-1;
		if (res<=0) continue;
		sum+=v[i][0]*res;
		v[i].clear();
	}
	cout<<sum<<endl;
}
signed main()
{
	T=read();
	while (T--) work();
	return 0;
}

代码二

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){int x;scanf("%lld",&x);return x;}
const int B=1e6+10;
const int inf=0x3f3f3f3f;
int T;
int n;
int a[B];
vector<int>v[1000009];
int fa[B];
int find(int x)
{
	if (fa[x]==x) return x;
	else return fa[x]=find(fa[x]);
}
struct node
{
	int u,v,x;
}e[B];
int cmp(node a,node b)
{
	return a.x<b.x;
}
int minxx[B]; 
void work()
{
	n=read();
	int tot=0;
	for (int i=1;i<=n;i++) a[i]=read(),fa[i]=i,minxx[i]=0x3f3f3f3f;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++) 
		{
			int x=read();
			if (!a[i] || !a[j]) continue;
			e[++tot]={i,j,x};
			minxx[i]=min(minxx[i],x);
		}
	}
	int sum=0;
	sort(e+1,e+1+tot,cmp);
	for (int i=1;i<=tot;i++)
	{
//		if (e[i].u==e[i].v) continue; 
		int u=find(e[i].u);
		int v=find(e[i].v);
		if (fa[u]==fa[v]) continue;
		fa[v]=u;
		sum+=e[i].x;
	}
	for (int i=1;i<=n;i++)
	{
		int res=a[i]-1;
		if (res<=0) continue;
		sum+=minxx[i]*res;
	}
	cout<<sum<<endl;
}
signed main()
{
	cin.tie(0); 
	T=read();
	while (T--) work();
	return 0;
}