抱歉您的并查集我没看懂......
by t162 @ 2019-10-04 20:14:25
您的这里
```
if(fa[edge[i].start] != fa[edge[i].end] )
{
fa[edge[i].start]=fa[edge[i].end];
k++;
ans=ans+edge[i].length;
}
```
明显是错的，您的并查集是用来干什么的？
by HLPP @ 2019-10-04 20:15:19
并查集也没路径压缩啊QAQ
by HLPP @ 2019-10-04 20:16:08
```cpp
#include <cstdio>
#include <algorithm>
using namespace std;
int fa[5010];int n,m;int a1,b1,c1;
int ans;
int cnt;
struct EDGE{
int start;
int end;
int length;
}edge[200000];
void add(int a, int b, int c)
{
cnt++;edge[cnt].start=a;edge[cnt].end=b;edge[cnt].length=c;
}
int upgrade(int x)
{
if(x==fa[x])return x;
x=upgrade(fa[x]);
}
bool pd( EDGE a,EDGE b)
{
return (a.length<b.length);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
fa[i]=i;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a1,&b1,&c1);
add(a1,b1,c1);
}
sort( edge+1,edge+m+1,pd);
// for(int i=1;i<=m;i++)
// {
// printf("%d\n",edge[i].length);
/// }
// printf("\n");
// for(int i=1;i<=n;i++)
/// {
// printf("%d\n",fa[i]);
// }
int k=0;
for(int i=1;i<=m;i++)
{
if(fa[edge[i].start] != fa[edge[i].end] )
{
fa[edge[i].start]=fa[edge[i].end];
for(int l=1;l<=n;l++)
{
upgrade(l);
}
k++;
ans=ans+edge[i].length;
}
if(k==n-1)
{
printf("%d",ans);
return 0;
}
}
}
```
除了第三个点其余全错了，还有两个mle
by return_dirt @ 2019-10-04 20:21:17
@[HLPP](/space/show?uid=192837)
一开始写了函数忘了调了
改了还是错……
by return_dirt @ 2019-10-04 20:21:50
@[return_dirt](/space/show?uid=180059) 并查集要改成
```
int upgrade(int x)
{
if(x==fa[x])return x;
fa[x]=upgrade(fa[x]);
}
```
还有
```
for(int l=1;l<=n;l++)
{
upgrade(l);
}
```
这样是没有必要的，只需要把并查集改成我上面写的就行了
还有
```
if(fa[edge[i].start] != fa[edge[i].end] )
```
您应该是upgrade那个start和end的fa来看是不是相等的
by HLPP @ 2019-10-04 20:26:26
@[HLPP](/space/show?uid=192837)
嗯……谢谢大佬，差不多懂了
不过如果我不
将全部点更新一遍的话怎么保证没有因为一次合并导致某一个集合被拆分呢？
比方说
如果
fa[1]=2
fa[2]=2
fa[3]=3
合并后
fa[1]=2
fa[2]=3
fa[3]=3
by return_dirt @ 2019-10-04 20:30:17
@[return_dirt](/space/show?uid=180059) 您upgrade的时候改成
```
int upgrade(int x)
{
if(x==fa[x])return x;
fa[x]=upgrade(fa[x]);
}
```
它就可以边找边更新了
```fa[x]=upgrade(fa[x])```
就是边找边更新
by HLPP @ 2019-10-04 20:32:10
@[HLPP](/space/show?uid=192837)
re了
2333
by return_dirt @ 2019-10-04 20:36:32
@[return_dirt](/space/show?uid=180059) 洛谷的评测总有些bug，刚刚我去IDE上运行了下您的代码它告诉我RE，然后我再DEV上正常运行...
by HLPP @ 2019-10-04 20:40:26