`Kruskal` 玄学做法 WA 求助
查看原帖
`Kruskal` 玄学做法 WA 求助
1286053
Nostopathy楼主2024/10/29 19:55
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    int x=0,F=1;
    char ch=getchar();
    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;
}
void write(int x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}
const int N=2E5+5, maxn=5E3+5;
struct san
{
	int U, V, W;
} l[N];
int n, m, sum, tot, f[maxn];
bool stsan(san a, san b)
{
	return a.W<b.W;
}
int fun(int k) { if(k==f[k]) return k; f[k]=fun(f[k]); return f[k]; }
bool mst()
{
	for(int i=1; i<=m; ++i)
	{
		int u=fun(l[i].U), v=fun(l[i].V);
		if(u==v) continue;
		f[u]=v, /* create tree */ tot+=l[i].W;
		if(sum==n-1) return 1; /* completed */
		++sum;
	}
	if(sum==n-1) return 1; return 0;
}
signed main(){
	//泥嚎,写题吧骚年
	n=read(), m=read(); for(int i=1; i<=m; ++i) l[i].U=read(), l[i].V=read(), l[i].W=read();
	stable_sort(l+1, l+n+1, stsan);
	for(int i=1; i<=n; ++i) f[i]=i;
	if(mst()) write(tot); else puts("orz");
	return 0;
}

2024/10/29 19:55
加载中...