蓝桥杯 城市建设 （Kruskal）

问题描述

栋栋居住在一个繁华的 C 市中，然而，这个城市的道路大都年久失修。市长准备重新修一些路以方便市民，于是找到了栋栋，希望栋栋能帮助他。

C 市中有 n 个比较重要的地点，市长希望这些地点重点被考虑。现在可以修一些道路来连接其中的一些地点，每条道路可以连接其中的两个地点。另外由于 C 市有一条河从中穿过，也可以在其中的一些地点建设码头，所有建了码头的地点可以通过河道连接。

栋栋拿到了允许建设的道路的信息，包括每条可以建设的道路的花费，以及哪些地点可以建设码头和建设码头的花费。

市长希望栋栋给出一个方案，使得任意两个地点能只通过新修的路或者河道互达，同时花费尽量小。

输入格式

输入的第一行包含两个整数 n, m，分别表示 C 市中重要地点的个数和可以建设的道路条数。所有地点从 1 到 n 依次编号。

接下来 m 行，每行三个整数 a, b, c，表示可以建设一条从地点 a 到地点 b 的道路，花费为 c 。若 c 为正，表示建设是花钱的，如果 c 为负，则表示建设了道路后还可以赚钱（比如建设收费道路）。

接下来一行，包含 n 个整数 w_1, w_2, …, w_n 。如果 w_i 为正数，则表示在地点i建设码头的花费，如果 w_i 为 -1 ，则表示地点i无法建设码头。

输入保证至少存在一个方法使得任意两个地点能只通过新修的路或者河道互达。

输出格式

输出一行，包含一个整数，表示使得所有地点通过新修道路或者码头连接的最小花费。如果满足条件的情况下还能赚钱，那么你应该输出一个负数。

样例输入

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

样例输出

9

思路

先说一下这道题的坑点吧！

原题中 市长希望栋栋给出一个方案，使得任意两个地点能只通过新修的路或者河道互达，同时花费尽量小。 这句话很容易让人误解为图中两点之间只能有一条路径，于是我就神奇的 WA 了。（一定要加上所有的负权边）

对于有码头的城市，我们为其创建一条从 $i$ 到 $0$ 的边，此时答案分两种情况：

• 结果只有陆路，不包含水路，即舍掉 $0$ 号点，此时按照 Kruskal 算法的思想，贪心找出连通所有城市且总花费最低的方案，记为 $ans_1$
• 结果包含水路，依然按照 Kruskal 算法的思想，找出连通所有城市以及 $0$ 号点的最小花费方案，记为 $ans_2$

则最终的答案为： $\min(ans_1,ans_2)$

AC 代码

#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <set>
#include <map>
#include <stack>

#define IO                       \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);

using namespace std;
const int maxn = 1e6 + 10;
typedef pair<int,int> P;

struct node{
    int from;
    int to;
    int cost;
    int next;
    friend bool operator<(const node &x,const node &y){
        return x.cost < y.cost;
    }
}edge[maxn];
int head[maxn],tot;
int n,m;

int fa[maxn],rk[maxn];

void init(){
    memset(head,-1,sizeof(head));
    tot = 0;
}

void addedge(int u,int v,int cost){
    edge[tot].from = u;
    edge[tot].to = v;
    edge[tot].cost = cost;
    edge[tot].next = head[u];
    head[u] = tot++;
}

void init_set(){
    memset(rk,0,sizeof(rk));
    for(int i=0;i<maxn;i++){
        fa[i] = i;
    }
}

int find_set(int x){
    if(fa[x]!=x)
        fa[x] = find_set(fa[x]);
    return fa[x];
}

bool union_set(int x,int y){
    x = find_set(x);
    y = find_set(y);
    if(x == y)return false;
    if(rk[x]>rk[y])
        fa[y] = x;
    else{
        fa[x] = y;
        if(rk[x] == rk[y])
            ++rk[y];
    }
    return true;
}

int result1(){  // 包含 0 号点
    init_set();
    int sum = 0;
    for(int i=0;i<tot;i++){
        int from = edge[i].from;
        int to = edge[i].to;
        bool flag = union_set(from,to);
        if(flag || edge[i].cost < 0){   // 负权边一定要加
            sum += edge[i].cost;
        }
    }
    return sum;
}

int result2(){  // 不包含 0 号点
    init_set();
    int sum = 0;
    for(int i=0;i<tot;i++){
        int from = edge[i].from;
        int to = edge[i].to;
        if(from == 0 || to == 0)continue;
        bool flag = union_set(from,to);
        if(flag || edge[i].cost < 0){   // 负权边一定要加
            sum += edge[i].cost;
        }
    }
    int cnt = 0;
    for(int i=1;i<=n;i++){
        if(find_set(i)==i)++cnt;
    }
    if(cnt != 1)return 1e9;
    return sum;
}

int main(){
    IO;
    init();
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v,c;
        cin>>u>>v>>c;
        addedge(u,v,c);
    }
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(x!=-1){
            addedge(i,0,x);
        }
    }
    sort(edge,edge+tot);
    cout<<min(result1(),result2())<<endl;
    return 0;
}