没人看吗，真的不会吗
by Stream月 @ 2019-06-05 16:46:09
@[Stream月](/user/156945) 代码发完，链接看不到
by RinkaSnow @ 2019-11-07 18:19:14
@[Stream月](/user/156945) **代码发完，链接看不到**
by limi_sanhua @ 2019-11-07 18:44:28
emmmmmmm……
by xwmwr @ 2019-11-07 18:45:55
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define $(i,a,n) for(int i =a;i<=n;i++)
#define _(i,a,n) for(int i =a;i>=n;i--)
#define clr(a) memset(a,0,sizeof(a))
inline ll read(){
ll ans = 0;
char last = ' ',ch = getchar();
while(ch<'0'||ch>'9') last = ch,ch = getchar();
while(ch>='0'&&ch<='9') ans = ans*10+ch-'0',ch = getchar();
if(last=='-') ans = -ans;
return ans;
}
const int MAXN = 2e5+5;
int n,m,bj = 1;
ll ans = 0;
struct Edge {
int x ,y ,z ;
}e[ MAXN ];
int ptr[MAXN];
bool cmp_z(const Edge &a,const Edge &b){
return a.z<=b.z;
}
int getPtr(int x){
if(x==ptr[x]) return x;
else return ptr[x] = getPtr(ptr[x]);
}
void kruskal(){
int f1 ,f2 , k=0;
$(i,1,n) ptr[i] = i;
$(i,1,m){
f1 = e[i].x , f2 = e[i].y;
f1 = getPtr(f1) , f2 = getPtr(f2);
if(f1!=f2){
ptr[f1] = f2;
ans+= e[i].z;
k++;
}
if(k==n-1) break;
}
if(k<n-1){
bj = 0;
printf("orz");
}
}
int main() {
//freopen("testdata.in","r",stdin);
//freopen("ans.out","w",stdout);
n = read(), m = read();
$(i,1,m) {
e[i].x = read() ,e[i].y = read() ,e[i].z = read() ;
}
std::sort(e+1,e+m+1,cmp_z);
kruskal();
if(bj) printf("%lld",ans);
return 0;
}
```
60分
by Stream月 @ 2019-11-07 20:30:39
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define $(i,a,n) for(int i =a;i<=n;i++)
#define _(i,a,n) for(int i =a;i>=n;i--)
#define clr(a) memset(a,0,sizeof(a))
inline ll read(){
ll ans = 0;
char last = ' ',ch = getchar();
while(ch<'0'||ch>'9') last = ch,ch = getchar();
while(ch>='0'&&ch<='9') ans = ans*10+ch-'0',ch = getchar();
if(last=='-') ans = -ans;
return ans;
}
using namespace std;
const int MAXN = 200005;
int n,m,bj = 1;
ll ans = 0;
struct Edge {
int x ,y ,z ;
}e[MAXN];
int ptr[MAXN];
bool cmp_z(const Edge &a,const Edge &b){
return a.z<b.z;
}
int getPtr(int x){
if(x==ptr[x]) return x;
else{
ptr[x] = getPtr(ptr[x]);
return ptr[x];
}
}
void kruskal(){
int f1 ,f2 , k=0;
$(i,1,n) ptr[i] = i;
$(i,1,m){
f1 = getPtr(e[i].x) , f2 = getPtr(e[i].y);
if(f1!=f2){
ptr[f1] = f2;
ans+= e[i].z;
k++;
}
if(k==n-1) break;
}
if(k<n-1){
bj = 0;
printf("orz");
return;
}
}
int main() {
//freopen("testdata.in","r",stdin);
//freopen("ans.out","w",stdout);
n = read(), m = read();
$(i,1,m) {
e[i].x = read() ,e[i].y = read() ,e[i].z = read() ;
}
sort(e+1,e+m+1,cmp_z);
kruskal();
if(bj) printf("%lld",ans);
return 0;
}
```
AC
by Stream月 @ 2019-11-07 20:31:23
@[tzxydby](/user/237660) 不好意思，多谢qwq
by Stream月 @ 2019-11-07 20:31:48
~~首先排除SPFA~~
by joker_0 @ 2019-11-07 20:32:21