@[wty20010315](/space/show?uid=17511) **N<=5000，M<=200000**的数据你只开1000条边当然炸
by 1124828077ccj @ 2017-04-28 20:53:13
楼上说得对啊，注意看数据范围
by OIer991215 @ 2017-04-28 22:36:37
@[2016陈常杰](/space/show?uid=14738) 知道了，谢谢dalao
by The_Key @ 2017-04-29 10:48:10
我也是
/\*
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
\*/
```cpp
#include<bits/stdc++.h>
using namespace std;
int fa[5001],n,m,sum,num,x,y;
struct node{
int s,e,w;
};
int gf(int x){
if(fa[x]==x) return x;
fa[x]=gf(fa[x]);
return fa[x];
}
bool camp(node a,node b){
if(a.w<b.w)
return 1;
return 0;
}
node b[200001];
void read(){
int i,j,k;
cin>>n>>m;
for(i=1;i<=m;i++)
cin>>b[i].s>>b[i].e>>b[i].w;
for(i=1;i<=n;i++)
fa[i]=i;
sort(b+1,b+m+1,camp);
for(i=1;i<=m;i++){
x=b[i].s;
y=b[i].e;
if(gf(x)==gf(y))
continue;
else{
sum+=b[i].w;
fa[y]=x;
num++;
if(num==n-1)
break;
}
}
cout<<sum<<endl;
}
int main()
{
read();
return 0;
}
```
by 雄鹰展翅 @ 2017-05-12 23:39:12
范围问题？
by SofanHe @ 2017-06-15 17:41:47