修路的方案終于確定了。市政府要求任意兩個公園之間都必須實現公路交通（并不一定有直接公路連接，間接公路相連也可以）。但是考慮到經濟成本，市政府希望錢花的越少越好。
你能幫助Vegetable找到給出的修路方案所需的最少花費嗎？
輸入 有T組測試數據。
每組包含一組N(0
#include<cstdio>#include<algorithm>using namespace std;#define maxn 110int par[maxn],rak[maxn];void set_init(){ for (int i = 0; i < maxn; ++i){ par[i] = i; rak[i] = 0; }}int set_find(int x){ return x == par[x]? x : par[x] = set_find(par[x]);}void set_union(int x,int y){ int tx = set_find(x); int ty = set_find(y); if (tx == ty) return ; if (rak[tx] > rak[ty]) par[tx] = ty; else{ par[ty] = tx; if (rak[tx] == rak[ty]) rak[tx]++; }}struct node { int from,to,cost;}spot[maxn];bool cmp(node a,node b){ if (a.cost!=b.cost) return a.cost < b.cost;}int main(){ int t; scanf("%d",&t); while (t--){ int n,m; scanf("%d%d",&n,&m); set_init(); for (int i = 0; i < m; ++i) scanf("%d%d%d",&spot[i].from,&spot[i].to,&spot[i].cost); sort(spot,spot+m,cmp); int res = 0; for (int i = 0; i < m; ++i){ int vf = spot[i].from; int vt = spot[i].to; if (set_find(vf) != set_find(vt)){ set_union(vf,vt); res += spot[i].cost; } } int fg = 0; for (int i = 2; i <= n; ++i){ if (set_find(i) != set_find(1)){ fg = 1; break; } } if (fg) 這題血虧 又是在判斷森林的地方出錯了 如果做出來積分賽好歹也能進前九 總的來說這次競賽狀態極差 竟然一直對著綁定的兩個節點搜索判斷 現在想想怎么可能判斷得出 這題坐標點仍然是1到n 思考 如果不是1到n 而是任意給的點 想法 標記已出現的點 判斷時搜索這些點 如果有重邊 想法 在把兩個節點并起來的時候 判斷是否已經在同一個跟節點上多做點題吧…
新聞熱點
疑難解答
