Kruskal 20分求助
查看原帖
Kruskal 20分求助
189287
打板自动机楼主2020/7/19 23:38

就过了1.3测试点 惨

#include<bits/stdc++.h>
using namespace std;
#define EMAX 200010
#define DMAX 5010
struct node
{
    int weight,f,t;
    bool operator<(const node& N){ return weight<N.weight;}
}edge[EMAX];

int uf[DMAX],es,dot;
int ufind(int node) { return (uf[node]==node)?node:uf[node]=ufind(uf[node]);}
int read()
{
    int ans=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {ans=(ans<<1)+(ans<<3)+(ch^48); ch=getchar();}
    return ans*f;
}
void kruskal()
{
    int ans=0,sum=0;
    for(int i=0;i<DMAX;i++) uf[i]=i;
    sort(edge,edge+es);
    for(int i=0;i<es;i++)
    {

        if(ufind(edge[i].f)==ufind(edge[i].t)) continue;

        uf[edge[i].t]=ufind(edge[i].f);

        ans+=edge[i].weight;
        sum++;
        if(dot==(sum+1)) break;

    }
    if(dot==(sum+1)) cout<<ans;
    else cout<<"orz";
    return;
}
int main()
{
    //dot 点数 es 边数
    dot=read(),es=read();
    for(int i=0;i<es;i++) edge[i].f=read(),edge[i].t=read(),edge[i].weight=read();
    kruskal();
    return 0;
}

2020/7/19 23:38
加载中...