C++最小生成树+并查集

解题思路:虚拟点0点，当码头只有一个时最后减掉，其他就是最小生成树和并查集

注意事项:可以挣钱的路不管树通不通都加

参考代码:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> f;
struct eg{
    int from,to,cost;
    eg(int From,int To,int Cost){
        from=From;
        to=To;
        cost=Cost;
    }
};
vector<eg> e;
int findd(int x){
    if(f[x]!=x)
        return f[x]=findd(f[x]);
    return x;
}
void unit(int x,int y){
    f[findd(x)]=findd(y);//y的根作为x的根节点的父节点
}
bool one(int x,int y){
    if(findd(x)==findd(y))
        return true;
    else return false;
}
bool comp(const eg& e1,const eg& e2){
        return e1.cost<e2.cost;//从小到大
}
int main(){
    int n,m,sum=0,a,b=-1,c,k=0,Cost;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>a>>b>>c;
        e.push_back(eg(a,b,c));
    }
    f.push_back(0);
    for(int i=1;i<=n;i++){
        cin>>a;
        if(a>0)
            e.push_back(eg(0,i,a));
        f.push_back(i);
    }
    sort(e.begin(),e.end(),comp);
    for(int i=0;i<e.size();i++){
       if(!one(e[i].from,e[i].to)||e[i].cost<0){//不是同一个集合
           unit(e[i].from,e[i].to);
           sum+=e[i].cost;
           if(e[i].from==0){
            k++;
            Cost=e[i].cost;
           }
       }
    }
    if(k!=1)
        cout<<sum;
    else
        cout<<sum-Cost;
}