题解 | #魏迟燕的自走棋#

题目链接：https://ac.nowcoder.com/acm/contest/9984/F

题目大意：给你n个人与m件装备，其中每个人都只能对应配一件装备，每件装备也只能配对应一个人。
每件装备可能对应的人有一个或者两个
同时每件装备具有wi点战斗力
问你最大能获得多少战斗力
思路：
感觉有点类似最大生成树
把每件装备的战斗力都当作边值，人的编号当作点
因为是要最大战斗力那么肯定要排序先最大的边进行合并
利用并查集来合并点，再利用辅助数组v[]判断点是否用过
同时要考虑一下自环的情况（就是每件装备只能对应一个人的时候）
如果这个点没用过就把它选上
AC代码：

#include <iostream>
#include <algorithm>
using namespace std;
struct node{
    int x,y;
    int w;
};
int fa[100010];
int vis[100010];
int findfa(int x){//并查集找根节点
    return fa[x]==x?x:fa[x]=findfa(fa[x]);
 }
 bool cmp(node a,node b){//把边排序
     return a.w>b.w;
 }
 node edge[100010];
 void init(){//并查集初始化
    for(int i=1;i<=100000;i++)fa[i]=i;
 }
int main()
{
    init();
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int k;
        cin>>k;
        if(k==1){//自环的情况
            int x,w;
            cin>>x>>w;
            edge[i].x=x;
            edge[i].y=x;
            edge[i].w=w;
        }else{
           int x,y,w;
           cin>>x>>y>>w;
           edge[i].x=x;
           edge[i].y=y;
           edge[i].w=w;
        }
    }
    sort(edge,edge+m,cmp);
    long long ans=0;
    for(int i=0;i<m;i++){
        int x=findfa(edge[i].x),y=findfa(edge[i].y);
        if(x!=y&&( !vis[x] || !vis[y])){//如果这两个人有一个人没装备就把装备分配给那个人
            ans+=edge[i].w;
            fa[y]=x;
            vis[x]=(vis[x] || vis[y]);//如果两个人都没装备那么他的根节点依然是属于没装备的状态，不然就是有装备的状态
        }else if(x==y&&!vis[x]){//自环，如果该点没用过直接加边
            ans+=edge[i].w;
            vis[x]=1;
        }
    }
    cout<<ans<<endl;
    return 0;
}