阿宁已被领养 @ 2022-09-26 19:40:43
记录如下，下了第三个测试点但是数据有点多看的眼都花了qwq
评测记录
数据还是不放了吧，太多了谁会手推五十个点的最小生成树啊qwq
代码如下
#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
ll n,m,x,y,z,f[1000000],ans=0,qwq=0;
struct gs
{
ll a,b,c;
}bian[1000000];
bool cmp(gs g,gs s)
{
return g.c<s.c;
}
ll find(ll x)
{
if(f[x]==x) return x;
else find(f[x]);
}
int main()
{
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;i++) f[i]=i;
for(ll i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&x,&y,&z);
bian[i].a=x;
bian[i].b=y;
bian[i].c=z;
}
sort(bian+1,bian+m+1,cmp);
//cout<<"start"<<endl;
for(ll i=1;i<=m;i++)
{
ll f1=find(bian[i].a),f2=find(bian[i].b);
if(f1!=f2)
{
//cout<<bian[i].a<<' '<<bian[i].b<<" "<<f1<<' '<<f2<<endl;
if(f1==bian[i].a) f1=f2;
f[bian[i].a]=f1;
f[bian[i].b]=f1;
ans+=bian[i].c;
}
}
for(ll i=1;i<=n;i++)//我想的是如果图不连通会有1+个根为自己的点,先纪录下来一个,再有多的就说明不连通了
{
if(f[i]==i&&qwq==1)
{
printf("orz");
return 0;
}
else if(f[i]==i) qwq++;
}
printf("%lld",ans);
return 0;
}不胜感激！！！！
by 8atemak1r @ 2022-09-26 19:48:17
@阿宁已被领养 判断无解你只需要在那个并查集里判断一下加进去的边是否等于 n-1 条就可以了，如果等于直接输出结果退出程序，如果整个 for 执行完了还没有结果那就无解
by 8atemak1r @ 2022-09-26 19:48:31
@阿宁已被领养 还有你这个并查集没看懂啊。
by 阿宁已被领养 @ 2022-09-26 19:50:22
@8atemak1r 并查集不是让很多节点的父亲是同一个就算是在同一个并查集里么
by 阿宁已被领养 @ 2022-09-26 19:51:35
@8atemak1r 可以设置一个记录加进去的边的变量ww在ans++的时候把ww+1最后与n+1比较判断么
by bktchizhi_fzh @ 2022-09-26 19:51:44
@阿宁已被领养 return x=find(f[x]);第十八行
by bktchizhi_fzh @ 2022-09-26 19:52:27
路径压缩
by Mr_ll @ 2022-09-26 20:08:22
#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
ll n,m,x,y,z,f[10000],ans=0,qwq=0;
int cnt;
struct gs
{
ll a,b,c;
}bian[1000000];
bool cmp(gs g,gs s)
{
return g.c<s.c;
}
ll find(ll x)
{
if(f[x]==x) return x;
else f[x]=find(f[x]);
}
int main()
{
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;i++) f[i]=i;
for(ll i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&x,&y,&z);
bian[i].a=x;
bian[i].b=y;
bian[i].c=z;
}
sort(bian+1,bian+m+1,cmp);
//cout<<"start"<<endl;
for(ll i=1;i<=m;i++)
{
ll f1=find(bian[i].a),f2=find(bian[i].b);
if(f1!=f2)
{
//cout<<bian[i].a<<' '<<bian[i].b<<" "<<f1<<' '<<f2<<endl;
//if(f1==bian[i].a) f1=f2;
//f[bian[i].a]=f1;
//f[bian[i].b]=f1;
if(f1>f2) swap(f1,f2);
f[f2]=f1;//有秩合并
ans+=bian[i].c;
cnt++;//cnt记已加入多少边
}
if(cnt==n-1) break;
}
// for(ll i=1;i<=n;i++)//我想的是如果图不连通会有1+个根为自己的点,先纪录下来一个,再有多的就说明不连通了
// {
// if(f[i]==i&&qwq==1)
// {
// printf("orz");
// return 0;
// }
// else if(f[i]==i) qwq++;
// }
if(cnt!=n-1) puts("orz");
else printf("%lld",ans);
return 0;
}by Mr_ll @ 2022-09-26 20:08:44
@阿宁已被领养
by 阿宁已被领养 @ 2022-09-26 20:14:48
@bktchizhi_fzh
@Mr_ll
@8atemak1r
已成功ACqwq
主要是find函数路径压缩和判断连通的问题
不胜感激orz