样例过不去!!!

P3366 【模板】最小生成树

clx201022 @ 2023-03-12 11:18:10

样例 input 4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3 my output 9 应该是七的

#include<bits/stdc++.h>
using namespace std;
struct bingchaji
{
  int f[5001],size[5001];
  inline int find(int x)
  {
    //return f[x]==x?x:f[x]=find(f[x]);
    while(x!=f[x])
        x=f[x]=f[f[x]];
    return x;
  }
  inline void merge(int x,int y)
  {
  x=find(x);
  y=find(y);
  if(size[x]>size[y])swap(x,y);
  f[x]=y;
  size[y]+=size[x];
  }
  bingchaji(int n)
  {
    for(int i=0;i<=n;i++)
    {
      f[i]=i;
      size[i]=1;
    }
  }
};
struct Edge
{
    int to,w,start;
};
vector<Edge>e;
inline bool cmp(Edge a,Edge b)
{
    return a.w<b.w;
}
int n,m,ans,bian;
int main()
{
    cin>>n>>m;
    bingchaji a(n);
    for(int i=1;i<=m;i++)
    {
        Edge bian;
        cin>>bian.start>>bian.to>>bian.w;
        e.push_back(bian);
    }
    sort(e.begin(),e.end(),cmp);
    for(int i=1,u,v;i<=m;i++)
    {
        u=a.find(e[i].start);
        v=a.find(e[i].to);
        if(a.find(e[i].start)==a.find(e[i].to))continue;
        ans+=e[i].w;
        a.merge(u,v);
        bian++;
        if(bian==n-1)break;
    }
    cout<<ans;
    return 0;
}

求调


by ZZQF5677 @ 2023-03-12 11:33:33

好像也好少了orz


by clx201022 @ 2023-03-12 11:35:52

@ZZQF5677 对啊,但样例里没有orz,求样例错误原因


by clx201022 @ 2023-03-12 14:16:09

AC了,AC了


|