本文主要是介绍J. 天空之城 (并查集求最短路) (2021牛客寒假算法基础集训营6)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
思路：根据题意显然知道可以利用并查集来求解，如若所有城市都在一个集合内，则表明能通往每个城市。该题明确说明走过的路再走不会再花时间，那么利用并查集就再简单不过，只不过在最开始选择路径时需要选择耗时最少的路，因此我们可以利用一个结构体排序来筛选一下。(注意备注里有提到该题时多组输入题型。)
代码实现：
#include<bits/stdc++.h>
//#define endl '\n'
#define null NULL
#define ll long long
#define int long long
#define pii pair<int, int>
#define lowbit(x) (x &(-x))
#define ls(x) x<<1
#define rs(x) (x<<1+1)
#define me(ar) memset(ar, 0, sizeof ar)
#define mem(ar,num) memset(ar, num, sizeof ar)
#define rp(i, n) for(int i = 0, i < n; i ++)
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define pre(i, n, a) for(int i = n; i >= a; i --)
#define IOS ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int way[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
using namespace std;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-6;
const ll mod = 1e9+7;
const int N = 2e5 + 5;inline void read(int &x){char t=getchar();while(!isdigit(t)) t=getchar();for(x=t^48,t=getchar();isdigit(t);t=getchar()) x=x*10+(t^48);
}struct node{int x, y, w;bool operator < (const node &x) const {return w < x.w;}
}g[N];int f[N];
int find(int x){if(x == f[x]) return x;return f[x] = find(f[x]);
}int n, m, val;
map<string, int> pos;
string a, b;signed main()
{IOS;while(cin >> n >> m){pos.clear();for(int i = 1 ; i <= n ; i ++) f[i] = i; //初始化并查集的父标记数组cin >> a;int tt = 0;for(int i = 1 ; i <= m ; i ++){cin >> a >> b >> val;if(!pos[a]) pos[a] = ++tt;if(!pos[b]) pos[b] = ++tt;g[i] = {pos[a], pos[b], val}; //建边}sort(g+1,g+m+1); //利用边的权值进行排序int ans = 0;for(int i = 1 ; i <= m ; i ++){int fx = find(g[i].x) , fy = find(g[i].y);if(fx == fy) continue;f[fx] = fy;ans += g[i].w;}int fa = find(f[1]) ; //找到根节点int flag = 0;for(int i = 1 ; i <= n ; i ++){if(find(f[i]) != fa){ //如果某个城市不连通cout << "No!" << endl;flag = 1;break;}}if(!flag) cout << ans << endl;}return 0;
}
这篇关于J. 天空之城 (并查集求最短路) (2021牛客寒假算法基础集训营6)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
