```
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define _for(i,a,b) for(long long i=a;i<=b;++i)
using namespace std;
typedef long long ll;
ll n,m;
ll fa[1005];
ll ans=0;
struct node{
ll u,v,w;
}a[100005];
ll cnt=0;
ll read(){
ll res=0,flag=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')flag=-1;
c=getchar();
}
while(isdigit(c)){
res=res*10+c-'0';
c=getchar();
}
return res*flag;
}
ll find(ll x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
bool cmp(node x,node y){
return x.w<y.w;
}
void kruskal(){
ll f1,f2,k=0;
_for(i,1,cnt){
f1=find(a[i].u);
f2=find(a[i].v);
if(f1!=f2){
k++;
ans+=a[i].w;
fa[f2]=f1;
if(k==n-1)return;
}
}
}
int main(){
ll x,l,r;
cin>>n>>m;
_for(i,1,n){
fa[i]=i;
}
_for(i,1,m){
l=read(),r=read(),x=read();
++cnt;
a[cnt].u=l;a[cnt].v=r;a[cnt].w=x;
}
sort(a+1,a+cnt+1,cmp);
kruskal();
cout<<ans<<endl;
return 0;
}
```
by かねき けん @ 2018-11-07 23:54:27
这个也行
```
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#define ll long long
#define _for(i,a,b) for(ll i=a;i<=b;++i)
using namespace std;
const ll N=1e6+5;
ll read(){
ll res=0,ff=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')ff=-1;
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+ch-'0';
ch=getchar();
}
return res*ff;
}
ll h[105],hn;
void print(ll x){
if(x<0){
putchar('-');
x=-x;
}
if(x==0)putchar('0');
while(x){
h[++hn]=x%10,x/=10;
}
while(hn){
putchar(h[hn--]^48);
}
}
ll n,m,ans;
struct node{
int to,dis;
bool operator <(const node&a)const{
return dis>a.dis;
}
};
int cnt;
vector<node>g[N];
priority_queue<node>q;
bool vis[N];
void prim(){
_for(i,0,g[1].size()-1){
q.push(g[1][i]);
}
vis[1]=true;cnt=n;
while(!q.empty()&&cnt){
node p=q.top();q.pop();
if(vis[p.to])continue;
vis[p.to]=true;ans+=p.dis;
_for(i,0,g[p.to].size()-1){
node k=g[p.to][i];
if(!vis[k.to]){
q.push(k);
}
}
}
}
int main(){
cin>>n>>m;
_for(i,1,m){
int x=read(),y=read(),z=read();
g[x].push_back((node){y,z});
g[y].push_back((node){x,z});
}
prim();
cout<<ans<<endl;
return 0;
}
```
by かねき けん @ 2018-11-07 23:55:07
@[SCZ大♂](/space/show?uid=33444) 常熟啥的，快读就够了……
by tocek_shiki @ 2018-11-07 23:59:36
快读吼啊
by NieR_Automata @ 2018-11-08 08:50:41
~~手写sort~~
by coyangjr @ 2018-11-08 14:46:54
@[fff团666](/space/show?uid=49562) 我加了快读啊。。。为什么被卡常喽
by znwyx @ 2018-11-08 21:27:01