dd
by chenxsir @ 2020-03-06 11:42:53
@[chenxsir](/user/218223) `for(int i=1;i<=5050;i++)smp[i]=i;`？
by andyli @ 2020-03-06 11:48:54
~~为什么要priority_queue啊~~
by SamariumPhosphide @ 2020-03-06 11:52:57
~~不能sort吗。。。~~
by SamariumPhosphide @ 2020-03-06 11:53:08
@[andyli](/user/84282) 并查集初始化啊。
我之前有份代码AC了。
```cpp
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct pp
{
int to,from,w;
};
struct cmp
{
bool operator ()(const pp a,const pp b) const
{
return a.w>b.w;
}
};
priority_queue<pp,vector<pp>,cmp> duil;
int n,m,f[200200],ans;
int find(int);
void add(int,int);
int main()
{
cin>>n>>m;
while(m--)
{
pp lsx;
cin>>lsx.to>>lsx.from>>lsx.w;
duil.push(lsx);
}
for(int i=0;i<=n;i++) f[i]=i;
while(!duil.empty())
{
pp lsx=duil.top();
//cout<<lsx.w<<" "<<lsx.from<<" "<<lsx.to<<endl;
duil.pop();
if(find(lsx.to)!=find(lsx.from))
{
add(lsx.to,lsx.from);
ans+=lsx.w;
}
}
cout<<ans;cin>>ans;
return 0;
}
int find(int x)
{
if(f[x]==x)return x;
return f[x]=find(f[x]);
}
void add(int x,int y)
{
int lsx=find(x);int lsy=find(y);
f[lsx]=lsy;
}
```
，感觉这个和我刚刚写的没啥区别啊。搞不懂
by chenxsir @ 2020-03-06 11:53:42
@[fürtän](/user/319914) sort要慢一点
by chenxsir @ 2020-03-06 11:55:02
@[chenxsir](/user/218223) ？
by __gcd @ 2020-03-06 11:58:56
@[chenxsir](/user/218223) 你代码的时间复杂度和sort一样都是$O(m\log m)$，但是你的常数明显要大
by __gcd @ 2020-03-06 11:59:57
我觉得sort更快呢.我没吸氧都比你快……
by SaturdayForever @ 2020-03-06 12:03:44
@[chenxsir](/user/218223) 并查集初始化您也不能这样初始化啊
by andyli @ 2020-03-06 12:05:24