魏迟燕的自走棋

思路

• 根据贪心的策略，优先装备战斗力大的装备。
• 用连通块的思想把符合装备的两人相连，如果是一人则自环
  利用连通块和st数组来维护这个人有没有装备

代码

// Problem: 魏迟燕的自走棋
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/9984/F
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
#define debug(a) cout<<#a<<":"<<a<<"\n"
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=100010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

int fa[N],depth[N];
void init(int n){
    for(int i=1;i<=n;i++) 
        fa[i]=i,depth[i]=1;
}
//查询树的根
int find(int x){
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}
//合并a和b所属的集合   
void unite(int a,int b){
    a=find(a),b=find(b);
    if(depth[a]==depth[b]){
        depth[a]=depth[a]+1;
        fa[b]=a;
    }
    else{
        if(depth[a]<depth[b]) fa[a]=b;
        else fa[b]=a;
    }
}
//判断a和b是否属于同一个集合
bool same(int a,int b){
    return find(a)==find(b);
}

struct node{
    int u,v;
    ll w;
}e[N];

bool cmp(node x,node y){
    return x.w>y.w;
}

bool st[N];

ll ans;

void solve(){
    int n,m;cin>>n>>m;
    init(n);
    for(int i=0;i<m;i++){
        int k;cin>>k;
        if(k==1){
            cin>>e[i].u>>e[i].w;
            e[i].v=e[i].u;
        }
        else{
            cin>>e[i].u>>e[i].v>>e[i].w;
        }
    }
    sort(e,e+m,cmp);
    for(int i=0;i<m;i++){
        int x=find(e[i].u),y=find(e[i].v);
        if(x!=y){
            if(st[x]&&st[y]) continue;
            unite(e[i].u,e[i].v);
            ans+=e[i].w;
            if(!st[x]&&!st[y]) continue;
            else if(!st[x]) st[x]=1;
            else st[y]=1;
        }
        else if(!st[x]){
            ans+=e[i].w;
            st[x]=1;
        }
    }
    cout<<ans<<"\n";
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}