EZOJ #393加倍的飞机

分析

从大到小考虑每个点

记录一个连通块中选了选了几个

如果选的小于siz则直接选否则不选

代码

#include<bits/stdc++.h>
using namespace std;
struct node {
    int x,y,z;
};
node d[100100];
int n,m,fa[100100],siz[100100],use[100100];
inline int sf(int x){return fa[x]==x?x:fa[x]=sf(fa[x]);}
inline bool cmp(const node x,const node y){return x.z>y.z;}
int main(){
    int i,j,k,Ans=0;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)fa[i]=i,siz[i]=1;
    for(i=1;i<=n;i++)scanf("%d%d%d",&d[i].x,&d[i].y,&d[i].z);
    sort(d+1,d+n+1,cmp);
    for(i=1;i<=n;i++){
      int x=d[i].x,y=d[i].y;
      if(sf(x)!=sf(y)){
          siz[sf(y)]+=siz[sf(x)];
          use[sf(y)]+=use[sf(x)];
          fa[sf(x)]=sf(y);
          if(use[sf(x)]<siz[sf(x)])use[sf(x)]++,Ans+=d[i].z;
      }else {
          if(use[sf(x)]<siz[sf(x)])use[sf(x)]++,Ans+=d[i].z;
      }
    }
    cout<<Ans;
    return 0;
}