城市建设【两遍克鲁斯卡尔算法求 MST 】

Lokinli

发布于 2023-03-09 14:00:44

1800

发布于 2023-03-09 14:00:44

文章被收录于专栏：以终为始

城市建设

Description

栋栋居住在一个繁华的C市中，然而，这个城市的道路大都年久失修。市长准备重新修一些路以方便市民，于是找到了栋栋，希望栋栋能帮助他。 C市中有n个比较重要的地点，市长希望这些地点重点被考虑。现在可以修一些道路来连接其中的一些地点，每条道路可以连接其中的两个地点。另外由于C市有一条河从中穿过，也可以在其中的一些地点建设码头，所有建了码头的地点可以通过河道连接。栋栋拿到了允许建设的道路的信息，包括每条可以建设的道路的花费，以及哪些地点可以建设码头和建设码头的花费。市长希望栋栋给出一个方案，使得任意两个地点能只通过新修的路或者河道互达，同时花费尽量小。

Input

输入的第一行包含两个整数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无法建设码头。输入保证至少存在一个方法使得任意两个地点能只通过新修的路或者河道互达。

Output

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

Sample Input 1

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

Sample Output 1

解析：问题需要考虑的是需要不需要建立码头，可以分成下面两种情况：

如果必须建立码头的情况，则只需要把码头每个码头看做和一个特殊点0点相连，这样就是一个普通的MST问题，跑一遍克鲁斯卡尔算法得到的 ans1 就是答案，原因是不建立码头没法全联通，不需要考虑建立或者不建立带来的花费问题。
如果不建立码头情况能够连通所有的点，那么会有两种情况：一种是1的情况，得到答案 ans1，二种是我们不考虑码头，这样子又变成了普通 MST 问题，跑一遍克鲁斯卡尔算法得到答案 ans2 ，最佳答案就是 min(ans1,ans2)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <bits/stdc++.h>
#include <queue>
#include <algorithm>
#include <map>
#include <cstdlib>
using namespace std;
#define inf 0x3f3f3f3f
int fa[10005];
int ans1, ans2;
int n,m;
int w[10005];
struct node
{

    int x,y;
    int cost;
} s[145605]; // 存放边权
// 排序
bool cmp(struct node a, struct node b)
{
    return a.cost < b.cost;
}
// 路径压缩，寻找父节点
int fin(int x)
{
    return x == fa[x] ? x : fa[x] = fin(fa[x]);
}

// 建立码头，生成MST
void kral_first()
{
    for (int i = 0; i <= n; i ++)
    {
        fa[i] = i;
    }
    sort(s,s+n+m,cmp);
    ans1 = 0;
//    for(int i = 0; i < n + m; i ++)printf("%d %d %d\n",s[i].x,s[i].y,s[i].cost);
    for(int i = 0; i < n + m; i ++)
    {
        if(s[i].cost == -inf) continue;
        int a = fin(s[i].x);
        int b = fin(s[i].y);
        if(a!=b || s[i].cost <= 0)
        {
            fa[a] = b;
            ans1 += s[i].cost;
//          printf("%d\n",ans1);
        }
    }

}
// 不建立码头，生成MST
void kral_second()
{
    for(int i = 0; i <= n; i ++)
    {
        fa[i] = i;
    }
    ans2 = 0;
    sort(s,s+n+m,cmp);
    for(int i = 0; i < n + m; i ++)
    {
        if(s[i].x == 0) continue; // 跳过所有码头
        int a = fin(s[i].x);
        int b = fin(s[i].y);
        if(a != b || s[i].cost <= 0)
        {
            fa[a] = b;
            ans2 += s[i].cost;
        }
    }

}
int main()
{
    int u,v,c;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i ++)
    {
        scanf("%d %d %d", &u, &v, &c);
        s[i].x=u;
        s[i].y=v;
        s[i].cost=c;
    }
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &w[i]);
        s[i+m-1].x = 0;
        s[i+m-1].y = i;
        if(w[i] == -1)
            s[i+m-1].cost=-inf;
        else s[i+m-1].cost = w[i];
    }
    kral_first();
    kral_second();
    int sum = 0;
    // 不建立码头，判断能否联通，如果能，则比较哪一种小。
    // 如果不建立码头，不能联通，则答案为 ans1。
    for(int i = 1; i <= n; i ++)
    {
        if(i == fa[i]) sum ++;
    }
    if(sum == 1) printf("%d\n",min(ans1,ans2));
    else printf("%d\n",ans1);

    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-07-05，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度