社区讨论
16分,请大佬看看这哪里错了
P1194买礼物参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lo1qifph
- 此快照首次捕获于
- 2023/10/23 01:20 2 年前
- 此快照最后确认于
- 2023/11/03 01:59 2 年前
CPP
#include <bits/stdc++.h>
using namespace std;
int n,m,cnt=0,sum=0,tot=1;
struct edge
{
int from,to,val;
bool operator <(const edge Com)const
{
return val<Com.val;
}
void getin(int I,int J)
{
int x;
scanf("%d",&x);
if(x&&I<J)
{
cnt++;
from=I;
to=J;
val=x;
}
}
};
edge ve[500*500+1];
int fa[501];
int fdx(int x)
{
if(fa[x]==x) return x;
return fa[x]=fdx(fa[x]);
}
void unxy(int x,int y)
{
fa[fdx(x)]=fdx(y);
}
void work()
{
for(int i=1;i<=cnt&&tot<=m;i++)
{
if(fdx(ve[i].from)!=fdx(ve[i].to))
{
++tot;
sum+=ve[i].val;
unxy(ve[i].from,ve[i].to);
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
ve[cnt].getin(i,j);
}
}
for(int i=1;i<=m;i++)
{
ve[i].from=0;
ve[i].to=i;
ve[i].val=n;
}
for(int i=1;i<=m;i++)
{
fa[i]=i;
}
sort(ve+1,ve+cnt+1);
work();
printf("%d",sum);
return 0;
}
谢谢!
回复
共 2 条回复,欢迎继续交流。
正在加载回复...