Gravatar
tat
积分:399
提交:106 / 465
把路按时间排序,加权size[i]表示 i 所属的并查集的个数 按顺序依次合并每条路 每次合并完判断当前并查集的size是否达到n

Gravatar
Richard
积分:286
提交:137 / 317

Gravatar
Hale
积分:2088
提交:510 / 1054

Gravatar
Hale
积分:2088
提交:510 / 1054
十五分钟搞定,复习kruscal

Gravatar
サイタマ
积分:1132
提交:302 / 714
prim也能过的说!!!

Gravatar
WHZ0325
积分:1231
提交:347 / 532
并查集的基础练习

Gravatar
O(1)
积分:310
提交:167 / 482
看错题。。

Gravatar
dateri
积分:1305
提交:587 / 1302
最小生成树的最大边一定是所有生成树中最小的。
因为kruskal算法保证在取到这条边之前构不成生成树

Gravatar
Hzoi_Yniverse
积分:1188
提交:610 / 1385
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1000;
struct Node{
int from,to,cost;
}a[100001];
bool comp(const Node &a,const Node &b){
return a.cost<b.cost;
}
int n,m,root[1001];
void Kruskal();
int Findroot(int);
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y,z;cin>>x>>y>>z;
a[i].from=x;a[i].to=t;a[i].cost=z;
}
Kruskal();
return 0;
}
void Kruskal(){
int ans=0,cnt=0;
for(int i=1;i<=n;i++){
root[i]=i;
}
sort(a+1,a+m+1,comp);
for(int i=1;i<=m;i++){
int x=a[i].from,y=a[i].to;
int rx=Findroot(x),ry=Findroot(y);
if(rx==ry) continue;
else{
root[rx]=ry;cnt++;
if(a[i].cost>ans) ans=a[i].cost;
}
if(cnt==n-1) break;
}
if
}
int Findroot(int x){
if(x!=root[x]){
root[x]=Findroot(root[x]);
}
return root[x];
}

Gravatar
水墨青花
积分:212
提交:100 / 316
用Kruskal求最小生成树即可

Gravatar
洛克索耶夫
积分:1236
提交:341 / 501
回复 @=_= :
说的没错~~

Gravatar
Sky_miner
积分:2790
提交:902 / 1646
Kruskal+cnt计数,如果循环到最后都没有 cnt = n -1 ;说明没有连通
输出-1,其他的就是个裸的最小生成树

Gravatar
乌龙猹
积分:1288
提交:469 / 784
居然把m打成了n

Gravatar
HouJikan
积分:1857
提交:596 / 1973
回复 @Hoskey :
写错了不知道多少次了= =看题不清楚作死的节奏

Gravatar
HouJikan
积分:1857
提交:596 / 1973
回复 @Hoskey :
写错了不知道多少次了= =看题不清楚作死的节奏

Gravatar
GDFRWMY
积分:318
提交:81 / 216
连MST都不会写了。。。
刷水太少了。。。。。。

Gravatar
cstdio
积分:4748
提交:1198 / 2108
奇葩地跪在0~n-1和1~n的问题上了……