实在不行就帮忙看一下Kruskal求最小生成树
我才70pt
```
#include<bits/stdc++.h>
using namespace std;
int n,m;
int u[200001],v[200001],w[200001];
int f[200001];
int sum,count1;
void quicksort(int left,int right)
{
if(left>right) return;
int i=left,j=right;
while(i!=j)
{
while(w[j]>=w[left] && i<j) j--;
while(w[i]<=w[left] && i<j) i++;
if(i<j)
{
swap(w[i],w[j]);
swap(u[i],u[j]);
swap(v[i],v[j]);
}
}
swap(w[i],w[left]);
swap(u[i],u[left]);
swap(v[i],v[left]);
quicksort(left,i-1);
quicksort(i+1,right);
}
int getf(int v)
{
return f[v]==v?v:f[v]=getf(f[v]);
}
int merge(int u,int v)
{
int t1=getf(u),t2=getf(v);
if(t1!=t2)
{
f[t1]=t2;
return 1;
}
return 0;
}
int main()
{
int i,j,k;
cin>>n>>m;
for(i=1;i<=m;i++)
cin>>u[i]>>v[i]>>w[i];
for(i=m+1;i<=2*m;i++)
{
u[i]=v[i-m];
v[i]=u[i-m];
w[i]=w[i-m];
}
for(i=1;i<=n;i++) f[i]=i;
quicksort(1,m);
for(i=1;i<=m;i++)
{
if(merge(u[i],v[i]))
{
sum+=w[i];
count1++;
}
if(count1==n-1)
break;
}
if(count1<n-1)
cout<<"orz";
else
cout<<sum;
return 0;
}
```
by 泰山飞狐 @ 2019-11-13 16:43:04
@[泰山飞狐](/user/112972)
我不会结构体排序，只好打一个手写快排
by 泰山飞狐 @ 2019-11-13 16:44:27
你硬要手写，又都写不对
我也没办法啊。。。
by TLE自动机 @ 2019-11-13 17:12:33
@[TLE自动机](/user/48744)
Kruskal总可以吧
by 泰山飞狐 @ 2019-11-13 17:14:52
@[泰山飞狐](/user/112972)
手写排序的话我只会归并，没写过快排
by TLE自动机 @ 2019-11-13 17:17:25
@[TLE自动机](/user/48744)
理解理解，我还是自己去查查吧。
不过有些事情别说的太直白，会引起反感的。
by 泰山飞狐 @ 2019-11-13 17:24:03
@[泰山飞狐](/user/112972) 把并查集路径压缩试试？
by 大耳朵图图 @ 2019-11-13 19:52:05
@[泰山飞狐](/user/112972) 将你kruskal里的```
return f[v]==v?v:f[v]=getf(f[v]);
```
改为```
f[v]=f[v]==v?v:f[v]=getf(f[v]);
return f[v];
```
by 大耳朵图图 @ 2019-11-13 19:54:18
如果不行我就没办法了，我也蒻
by 大耳朵图图 @ 2019-11-13 19:54:49
好像就不关路径压缩的事。。。
by 大耳朵图图 @ 2019-11-13 19:56:01