蓝桥杯历届试题-城市建设 最小生成树 并查集 AC思路

解题思路:

        本题的思路就是处理好了码头，就是求最小生成树：
        1.处理码头：虚拟一个城市0，0与i城市建立码头的价值就等于w[i]

        2.建立最小生成树MST

注意事项:
        1.处理码头的时候，如果w[i]=-1，则不要加入这条边，或者设置w[i]=inf

        2.建立最小生成树的时候，如果a,b两条边的价值w[a][b]的小于0，则不管是否连通，都要将这条边加入MST（题中求最小价值）

        3.如果与城市0连接只有一条边，则不需要城市0，答案需要减去这条边的价值

参考代码:

#include <vector>
#include <iostream>
#include <cstdio>
#include <algorithm>

#define _for(i,a,b) for(int i=a;i<b;i++)
#define inf (1<<28)
using namespace std;

typedef long long LL;

struct edge{
    int a,b,w=inf;
    bool operator < (const edge& o) const{
        return w<o.w;
    }
};

edge es[150005];
int w[10005],h[10005],vis[10005];

int _find(int x){
    return x==h[x]?x:(h[x]=_find(h[x]));
}

int main() {
    int n,m,ans=0;
    scanf("%d%d",&n,&m);
    _for(i,1,m+1){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(c<es[i].w){
            es[i].a=a;
            es[i].b=b;
            es[i].w=c;
        }
    }
    //1..将码头添加进边集
    _for(i,1,n+1){
        scanf("%d",&w[i]);
        if(w[i]!=-1){
            es[++m].a=0;
            es[m].b=i;
            es[m].w=w[i];
        }
    }
    //2..建立MST
    vector<int> G;
    _for(i,0,n+1)h[i]=i;
    sort(es+1,es+m+1);
    _for(i,1,m+1){
        int a=es[i].a,b=es[i].b,c=es[i].w;
        int x=_find(a),y=_find(b);
        if(x!=y||c<=0){
            if(a==0)G.push_back(i);
            h[x]=y;
            ans+=c;
        }
    }
    if(G.size()==1)ans-=es[G[0]].w;
    cout<<ans<<endl;
}