- 題目大意

? ??某地發(fā)洪水，導(dǎo)致某些城市被淹而消失，現(xiàn)在想把剩下的零散的城市通過(guò)修路連接起來(lái)，已知現(xiàn)在有部分城市是連通的。可選擇修的路有m條，城市總共有n個(gè)，給出了m條路的起點(diǎn)終點(diǎn)和修路花費(fèi)，問(wèn)最少可花多少錢(qián)能保證所有的城市連通。

- 解題思路

? ?可以用kruskal。把邊權(quán)排序然后并查集添加邊即可。

- 代碼

#include<algorithm> #include<cstdio> using namespace std; int fa[505];struct Edge {int u, v, w;bool operator<(const Edge &rhs)const {return w < rhs.w;} }e[25005]; void init(int n) {for (int i = 1; i <= n; i++)fa[i] = i; }int find(int x) {if (x == fa[x])return x;else{return fa[x] = find(fa[x]);} }bool Union(int x, int y) {int fx = find(x), fy = find(y);if (fx == fy)return false;else{fa[fx] = fy;return true;} }void kruskal(int m,int k) {int sum = 0;sort(e, e + m);for (int i = 0; i < m; i++){int u = e[i].u, v = e[i].v, w = e[i].w;if (Union(u, v)){sum += w;k--;}}if (!k)printf("%d\n", sum);else{printf("-1\n");} } int main() {int n,m,t,p,q,c,k,tmp;scanf_s("%d",&t);while (t--){scanf_s("%d%d%d",&n,&m,&k);init(n);for (int i = 0; i < m; i++)scanf_s("%d%d%d",&e[i].u,&e[i].v,&e[i].w);tmp = n-1;for (int j = 0; j < k; j++){scanf_s("%d%d",&p,&q);while (--p){scanf_s("%d", &c);if (Union(q,c)){tmp--;}}}kruskal(m, tmp);}return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/alpacadh/p/8449434.html

總結(jié)

以上是生活随笔為你收集整理的D - Connect the Cities (HDU - 3371)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。