城市建设AC代码(kruskal算法+并查集)

对于本题样例

虚构地点6连接1,2,3,4,5，从而代替码头的功能(例如1,2,3，建设码头，等价于6站点建设三座联通1,2,3,的道路)

5 5
1 2 4
1 3 -1
2 3 3
2 4 5
4 5 10
-1 10 10 1 1

我们使用kruskal算法：

选取花费最低的路径1-3，此时总花费sum=-1；

已连接站点：1-3

继续取最小值的路径6-4,此时总花费sum=0；

已连接站点：1-3,6-4

继续取最小值的路径6-5,此时总花费sum=1；

已连接站点：1-3,6-4-5

继续取最小值的路径2-3,此时总花费sum=4；

已连接站点：1-2-3,6-4-5

继续取最小值的路径1-2，1和2已连接，不操作

继续取最小值的路径2-4此时总花费sum=9；

已连接站点：1-2-3-4-5-6

故sum=9

特别注意：1.题目所求为最大花费，因此只要道路的花费小于0，不论站点是否已有道路，都应该在建设道路

                 2.如果出现代替码头城市只连接一个站点的情况(即只建了一个码头)，应该将改码头的花费减去

                 3.提前对所有道路价值排序（只能用快速排序，否则会超时），且对于码头花费小于0的不进行排序

全代码如下（排序部分抄了大佬作业）：

#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
class Node
{
public:
	int a;
	int b;
	int c;
};
Node node[200001];
int n, m, w;
int fa[100001];
vector<Node>e;
void ini()
{
    for (int i = 1; i <= n+1; i++)
    {
        fa[i] = i;
    }
}
int find(int i)
{
    if (fa[i] == i)
        return i;
    else
    {
        fa[i] = find(fa[i]);
        return fa[i];
    }
}
void unionn(int x,int y)
{
    int _x = find(x);
    int _y = find(y);
    fa[_x] = _y;
}
bool comp(const Node& e1, const Node& e2) {
    return e1.c < e2.c;//从小到大
}
int main()
{
	cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> node[i].a >> node[i].b >> node[i].c;
        e.push_back(node[i]);
    }
    int t = m;
    for (int i = 1; i <= n; i++)
    {
        cin >> w;
        if (w != -1)
        {
            node[t].a = n + 1;
            node[t].b = i;
            node[t].c = w;
            e.push_back(node[t]);
            t++;
        }
    }
    sort(e.begin(),e.end(),comp);
    ini();
    int sum = 0;
    int i = 0;
    int j = 0;
    int temp = 0;
    for (; i < e.size(); i++)
    {
        if (e[i].c <= 0)
        {
            if (e[i].a != n + 1)
            {
                sum += e[i].c;
                unionn(e[i].a, e[i].b);
            }
        }
        else
        {
            break;
        }
    }
    for (; i < t; i++)
    {
        if (find(e[i].a) != find(e[i].b))
        {
            if (e[i].a == n + 1)
            {
                j++;
                temp = e[i].c;
            }
            if (j >= 2)
                break;
            sum += e[i].c;
            unionn(e[i].a, e[i].b);
        }
    }
    for (; i < t; i++)
    {
        if (find(e[i].a) != find(e[i].b))
        {
            sum += e[i].c;
            unionn(e[i].a, e[i].b);
        }
    }
    if (j == 1)
        sum-=temp;
    cout << sum;
	return 0;
}