蓝桥杯历届试题-城市建设 （C++代码）

解题思路:





注意事项:





参考代码:

#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#include <iostream>  
using namespace std;  
  
const int maxn = 10000 + 10;  
const int maxm = 100000 + 20000;    //还有与河相连的路，开大点  
  
int fa[maxn];  
//Find函数查找x的祖先  
int Find(int x)  
{  
    return x == fa[x] ? x : fa[x] = Find(fa[x]);  
}  
  
struct Road  
{  
    int u, v, w;  
    bool operator < (const Road& t) const   //按w由小到大排序  
    {  
        return w < t.w;  
    }  
} road[maxm];  
// kruskal算法求 m条边的最小生成树  
int kruskal(int m)  
{  
    int sum = 0;  
    for (int i = 0; i < m; i++)  
    {  
        int tx = Find(road[i].u), ty = Find(road[i].v);  
        if (tx != ty || road[i].w < 0) //注意此处road[i].w<0时也要建，赚钱的活当然干喽  
        {  
            sum += road[i].w;  
            fa[tx] = ty;  
        }  
    }  
    return sum;  
}  
  
int main()  
{  
    int n, m, x, ans;  
    scanf("%d%d", &n, &m);  
    for (int i = 0; i < m; i++)  
        scanf("%d%d%d", &road[i].u, &road[i].v, &road[i].w);  
  
    int cnt = 0;  
    for (int i = 1; i <= n; i++) //将河当为0点，保存边  
    {  
        scanf("%d", &x);  
        if (x != -1)  
        {  
            road[m + cnt].u = 0;  
            road[m + cnt].v = i;  
            road[m + cnt].w = x;  
            cnt++;  
        }  
    }  
    for (int i = 0; i <= n; i++) fa[i] = i;  //初始化并查集，自成连通分量  
    for (int i = 0; i < m; i++)          //不考虑建码头，看能否生成最小生成树  
    {  
        int tx = Find(road[i].u), ty = Find(road[i].v);  
        fa[tx] = ty;  
    }  
    for (x = 2; x <= n; x++) if (Find(1) != Find(x)) break;  //不建码头不能生成  
    if (x == n + 1)         //不建码头可以生成  
    {  
        for (int i = 0; i <= n; i++) fa[i] = i;  
        sort(road, road + m);  
        ans = kruskal(m);           //不建码头  
        for (int i = 0; i <= n; i++) fa[i] = i;  
        sort(road, road + m + cnt);  
        printf("%d\n", min(ans, kruskal(m + cnt))); //取不建与建的较小的  
    }  
    else            //只能建码头了！  
    {  
        for (int i = 0; i <= n; i++) fa[i] = i;  
        sort(road, road + m + cnt);  
        printf("%d\n",  kruskal(m + cnt));  
    }  
    return 0;  
}