一棵只需要n-m条边的最小生成树
#include<iostream> #include<string> #include<cstdio> #include<set> #include<stack> #include<list> #include<vector> #include<queue> #include<algorithm> #include<cstring> #include<cmath> #include<fstream> using namespace std; typedef long long ll; //ifstream cin; const int maxn = 510; int n,m; double x[maxn],y[maxn]; inline double getdis(int u,int v){ double i = x[u] - x[v],j = y[u] - y[v]; return sqrt(i * i + j * j); } struct node{ int u,v; double dis; bool operator < (const node &a) const{ return dis < a.dis; } }; vector<node> e; int fa[maxn]; int find(int x){ if (x == fa[x]) return x; else return fa[x] = find(fa[x]); } double kruskal(){ double ans = 0; for(int i = 0;i < n;++i) fa[i] = i; int sum = n,k = 0; while(sum > m){ int u = find(e[k].u),v = find(e[k].v); double dis = e[k].dis; if (u != v){ fa[u] = v; ans = dis; sum--; } k++; } return ans; } void init(){ cin >> m >> n; for(int i = 0;i < n;++i){ cin >> x[i] >> y[i]; } e.clear(); for(int i = 0;i < n - 1;++i) for(int j = i + 1;j < n;++j) e.push_back({i,j,getdis(i,j)}); sort(e.begin(),e.end()); double t = kruskal(); printf("%.2f\n",t); } int main(){ //cin.open("in.txt"); int t; cin >> t; while(t--){ init(); } }