有n个城市,有m条线路,每条线路a,b,len表示a到b的线路需要花费len的费用维修,要求能将所有城市联通的最小维修花费
按照排序排一下然后利用并查集解决
#include <iostream> #include <set> #include <string.h> #include <algorithm> using namespace std; struct node { int a; int b; int len; }road[500*500+100]; int father[1111]; int cmp(node a,node b) { return a.len<b.len; } int findf(int x) { if(father[x]==x) { ; } else father[x]=findf(father[x]); return father[x]; } int n,m; int main() { /* 有n个城市,有m条线路,每条线路a,b,len表示a到b的线路需要花费len的费用维修,要求能将所有城市联通的最小维修花费 按照排序排一下? */ int t; cin>>t; while (t--) { cin>>n>>m; for(int i=0;i<m;i++) { cin>>road[i].a>>road[i].b>>road[i].len; } sort(road,road+m,cmp); int sum=0; for(int i=0;i<n;i++)father[i]=i; for(int i=0;i<m;i++) { int fff=findf(road[i].a); int xxx=findf(road[i].b); if(fff!=xxx) { father[fff]=xxx; sum+=road[i].len; } } cout<<sum<<endl; } return 0; }