Kruskal 求最小生成树+ 并查集

解题思路:   看不加码头能不能构成最小生成树，如果不可以，则答案为加上码头和建路的最小生成树， ，，，如果可以，则在不加码头和  加上码头的最小生成树取最小值

注意事项:建议把初始化码头和把码头的边加到边集中写在一个循环，不然会超时

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e4 + 10, M = 1e5 + 10, INF = 0x3f3f3f3f;
int p[N], n, m, wi[N];
struct Edge {
    int a, b, w;
    //将边集按权值大小排序
    bool operator < (const Edge& W)const {
        return w < W.w;
    }
}e[M];

//并查集
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int Kruskal(int node, int length)
{
    int res = 0;
//初始化并查集
    for (int i = 0; i <= node; i++)   p[i] = i;
    sort(e, e + length);
    int cnt = 0;
    for (int i = 0; i < length; i++)
    {
        int a = e[i].a, b = e[i].b, c = e[i].w;
        a = find(a), b = find(b);
        //如果两个点不连通，将其连起来
        if (a!=b)
        {
            p[a] = find(b);
            res += c;
            cnt++;
        }
        //如果两个点连通但是c<0即是赚钱的，也要加上
        else if (c < 0)
            res += c;
    }
//如果不能构成连通图，则返回INF
    if (cnt < n - 1) return INF;
    return res;
}
int main()
{
    scanf("%d %d", &n, &m);
    int cnt = m, ans;
    //边集初始化
    for (int i = 0; i < m; i++)
    {
        int x, y, w;
        scanf("%d %d %d", &x, &y, &w);
        e[i] = { x,y,w };
    }
    int t = Kruskal(n, m);
    //加上码头
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &wi[i]);
        if (wi[i] != -1)
        {
            e[cnt].a = 0;
            e[cnt].b = i;
            e[cnt].w = wi[i];
            cnt++;
        }
    }
    //建路构成不了连通图，此时要加上码头
    if (t == INF)
    {
        ans = Kruskal(n + 1, cnt);
    }
    //建路可以构成联通图，则在两个结果中取小的   
    else
    {
        ans = min(t, Kruskal(n + 1, cnt));
    }

    cout << ans << endl;
    return 0;
}