求调wa
查看原帖
求调wa
1122530
elpsconr楼主2024/8/18 17:43

感觉思路没问题,为啥wa了33个点

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define tul tuple<int,int,int>
#define all(x) x.begin(),x.end()
#define cy cout<<"Yes"<<endl
#define cn cout<<"No"<<endl
#define lc rt<<1
#define rc rt<<1|1
const int N=3e5+6,yyx=998244353;
int n,m;
set<int> s[N];
int k[N],c[N],p[N];
struct DSU{
    vector<int> fa,sz;
    DSU(int n){
      fa.resize(n+1);
      sz.resize(n+1,1);
      iota(fa.begin(),fa.end(),0);
    }
    int find(int x){
      return x==fa[x]?x:fa[x]=find(fa[x]);
    }
    bool same(int x,int y){
      int px=find(x),py=find(y);
      return px==py;
    }
    void merge(int x,int y){
      int px=find(x),py=find(y);
      if(px!=py){
        fa[px]=py;
        sz[py]+=sz[px];
      }
    }
    int size(int x){
      return sz[find(x)];
    }
};
inline void solve(){
  cin>>n>>m;
  for(int i=1;i<=m;++i){
    cin>>k[i]>>c[i];
    for(int j=1;j<=k[i];++j){
       int a;cin>>a;
       s[i].insert(a);
    }
  }
  for(int i=1;i<=m;++i) p[i]=i;
  sort(p+1,p+1+m,[&](int x,int y){
    return c[x]<c[y];
  });
  DSU dsu(n+1);
  int ans=0,x=*s[p[1]].begin();
  for(int i=1;i<=m;++i){
    int id=p[i];
    for(auto a:s[id]){
        if(dsu.same(x,a)) continue;
        dsu.merge(a,x);ans+=c[id];
    }
    //cout<<c[id]<<endl;
  }
  int ok=1;
  for(int i=1;i<=n;++i){
    if(!dsu.same(i,x)){
        //cout<<i<<endl;
        ok=0;break;
    }
  }
  if(ok) cout<<ans<<endl;
  else cout<<-1<<endl;
}
signed main(){
  cin.tie(0)->sync_with_stdio(0);
  //freopen("D://321//in.txt","r",stdin);
  //freopen("D://321//out.txt","w",stdout);
  int _=1;
  //cin>>_;
  while(_--)
  solve();
  return 0;
}
2024/8/18 17:43
加载中...