我直接贴我最小生成树的板子了,
为红名大佬献丑了。
```
#include <bits/stdc++.h>
using namespace std;
const int MAXM=200001;
const int MAXN=5001;
int node[MAXN];
int n,m;
long long check=1,ans;
struct info
{
int weight;
int from;
int to;
info(int a,int b,int c):from(a),to(b),weight(c)
{}
};
vector<info>arc;
inline int read(void)
{
char ch=getchar();
int f=1,x=0;
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x*10)+(ch-'0');
ch=getchar();
}
return x*f;
}
int find(int p)
{
if(node[p]==p)
return p;
else
return node[p]=find(node[p]);
}
void change(int x,int y)
{
x=find(x);
y=find(y);
if(x==y)
return ;
node[x]=y;
return ;
}
bool queryl(int x,int y)
{
return (find(x)==find(y));
}
bool cmp(const info& a,const info& b)
{
if(a.weight!=b.weight)
return (a.weight<b.weight);
else
return(a.from<b.from);
}
int main(void)
{
n=read();
m=read();
for(int i=1;i<=n;i++)
node[i]=i;
int r1,r2,r3;
bool f=false;
for(int i=0;i<m;i++)
{
r1=read();
r2=read();
r3=read();
arc.push_back(info(r1,r2,r3));
}
sort(arc.begin(),arc.end(),cmp);
bool flag=false;
for(int i=0;i<m;i++)
{
if(!queryl(arc[i].from,arc[i].to))
{
check++;
change(arc[i].from,arc[i].to);
ans+=arc[i].weight;
}
if(check==n)
{
flag=true;
break;
}
}
if(flag)
cout << ans;
else
cout << "orz";
return 0;
}
```
by 空銀子 @ 2019-02-18 00:15:29