QS Network ZOJ - 1586 板子题
标签：style mes main col ret div ++ ace double
#include
#include
using namespace std;
const int N=1e6+10;
struct edge{
int a,b;
double w;
}e[N];
int p[N];
int a[N];
int n;
bool cmp(edge a,edge b)
{
return a.wb.w;
}
int find(int x)
{
if(p[x]!=x)
p[x]=find(p[x]);
return p[x];
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i)
p[i]=i;
for(int i=1;i)
cin>>a[i];
int num=0;
for(int i=1;i)
for(int j=1;j)
{
int len;
cin>>len;
if(i!=j)
{
e[num].a=i;
e[num].b=j;
e[num++].w=len+a[i]+a[j];
}
}
sort(e,e+num,cmp);
int sum=0;
for(int i=1;i)
{
int a=find(e[i].a);
int b=find(e[i].b);
int w=e[i].w;
if(a!=b)
{
p[a]=b;
sum+=w;
}
}
coutendl;
}
return 0;
}
QS Network ZOJ - 1586 板子题
标签：style mes main col ret div ++ ace double
原文地址：https://www.cnblogs.com/QingyuYYYYY/p/12240156.html
评论