$\color{Cyan}\text{Kruskal}$大法好：
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, x, y, z, f[2000010], line, side, sum;
inline int read () {
char ch = getchar();
int x = 0, f = 1;
while (ch < '0' || ch >'9') {
if(ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
x = x * 10 + (ch ^ 48), ch = getchar();
return x * f;
}
struct Point {
int u, v, w;
} po[2000010];
bool sorting_cmp(const Point &a,const Point &b) {
return a.w < b.w;
}
inline int find(int x) {
if(f[x] == 0) return x;
else return f[x] = find(f[x]);
}
int main() {
n = read(), m = read();
for(int i = 1; i <= m; ++i) {
x = read(), y = read(), z = read();
po[line].u = x, po[line].v = y, po[line].w = z;
line++;
}
sort(po, po + line, sorting_cmp);
for(int i = 0; i < line; ++i) {
int t = po[i].w,
ufa = find(po[i].u), vfa = find(po[i].v);
if(ufa != vfa) {
sum += t;
f[ufa] = vfa;
line++;
}
if(line == n - 1) break;
}
cout << sum;
return 0;
}
```
by Eason_AC @ 2019-03-31 13:51:06
```c
#include <iostream>
using namespace std;
const int N=5005;
const int M=400005;
const int INF=100000000;
struct node{
int num,next,weight;
}e[M];
struct minedges{
int u,cost;
}t[M];
int g[M],n,m,avail;
int cnt,ans;
void ins(int x,int y,int w){
avail++;
e[avail].num=y;
e[avail].weight=w;
e[avail].next=g[x];
g[x]=avail;
}
void init(){
cin>>n>>m;
for(int i=1;i<=n;i++)g[i]=-1;
for(int i=1;i<=m;i++){
int x,y,w;
cin>>x>>y>>w;
ins(x,y,w);
ins(y,x,w);
}
}
void create(int x){
for(int i=1;i<=n;i++){
t[i].u=x;
t[i].cost=INF;
}
for(int i=g[x];i!=-1;i=e[i].next){
t[e[i].num].u=x;
t[e[i].num].cost=min(t[e[i].num].cost,e[i].weight);
}
t[x].u=0;
t[x].cost=0;
int lowl=x;
for(int i=1;i<n;i++){
int lowcost=INF;
for(int j=1;j<=n;j++){
if(t[j].cost<=0)continue;
if(t[j].cost<lowcost){
lowcost=t[j].cost;
lowl=j;
}
}
if(t[lowl].cost>0){
ans+=t[lowl].cost;
t[lowl].cost*=-1;
cnt++;
}
for(int j=g[lowl];j!=-1;j=e[j].next){
if(t[e[j].num].cost<=0)continue;
if(t[e[j].num].cost>e[j].weight){
t[e[j].num].u=lowl;
t[e[j].num].cost=e[j].weight;
}
}
}
}
int main(){
init();
create(1);
if(cnt<n-1)cout<<"orz"<<endl;
else cout<<ans<<endl;
return 0;
}
```
by Maxliu @ 2019-03-31 14:11:48
@[The_Chosen_One](/space/show?uid=107372) 您边数组开小了（P.S.一般RE都是数组开小了）
by Maxliu @ 2019-03-31 14:12:43
@[Maxliu](/space/show?uid=107614) 好的我试试，谢谢
by The_Chosen_One @ 2019-03-31 17:12:01
@[Maxliu](/space/show?uid=107614) 好像并没有什么变化
by The_Chosen_One @ 2019-03-31 17:13:51
您把边和点的数组大小开反了（~~当然对于我这种蒟蒻来说全开到最大就好了233~~）
by Maxliu @ 2019-03-31 19:45:30
@[The_Chosen_One](/space/show?uid=107372)
by Maxliu @ 2019-03-31 19:45:41
我给您的是AC代码
by Maxliu @ 2019-03-31 19:47:05
```
#include <iostream>
using namespace std;
const int N=5005;
const int M=400005;
const int INF=100000000;
struct node{
int num,next,weight;
}e[M];//MMMMMMMMMMMMMMMMMMMMMM
struct minedges{
int u,cost;
}t[M];//MMMMMMMMMMMMMMMMMMMMMM
int g[M],n,m,avail;
int cnt,ans;
void ins(int x,int y,int w){
avail++;
e[avail].num=y;
e[avail].weight=w;
e[avail].next=g[x];
g[x]=avail;
}
void init(){
cin>>n>>m;
for(int i=1;i<=n;i++)g[i]=-1;
for(int i=1;i<=m;i++){
int x,y,w;
cin>>x>>y>>w;
ins(x,y,w);
ins(y,x,w);
}
}
void create(int x){
for(int i=1;i<=n;i++){
t[i].u=x;
t[i].cost=INF;
}
for(int i=g[x];i!=-1;i=e[i].next){
t[e[i].num].u=x;
t[e[i].num].cost=min(t[e[i].num].cost,e[i].weight);
}
t[x].u=0;
t[x].cost=0;
int lowl=x;
for(int i=1;i<n;i++){
int lowcost=INF;
for(int j=1;j<=n;j++){
if(t[j].cost<=0)continue;
if(t[j].cost<lowcost){
lowcost=t[j].cost;
lowl=j;
}
}
if(t[lowl].cost>0){
ans+=t[lowl].cost;
t[lowl].cost*=-1;
cnt++;
}
for(int j=g[lowl];j!=-1;j=e[j].next){
if(t[e[j].num].cost<=0)continue;
if(t[e[j].num].cost>e[j].weight){
t[e[j].num].u=lowl;
t[e[j].num].cost=e[j].weight;
}
}
}
}
int main(){
init();
create(1);
if(cnt<n-1)cout<<"orz"<<endl;
else cout<<ans<<endl;
return 0;
}
```
by Maxliu @ 2019-03-31 19:48:01
@[Maxliu](/space/show?uid=107614) 真谢谢您了，抱歉初三复习忙没及时回
by The_Chosen_One @ 2019-04-05 23:05:15