1821: [JSOI2010]Group 部落划分 Group
链接
分析：
二分，然后把小于这条边的全连上，然后判断联通块的个数，如果<k，那么说明mid太大，否则说明mid太小。
其实有更奇妙的思路，从小的往大的加边，一旦加到使联通块的个数==k-1了，说明k个联通块已经构造出来了，再加入这一条就不满足了，这一条边就是答案。
代码：
二分
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 ?5 inline int read() { 6 ????int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch==‘-‘)f=-1; 7 ????for (;isdigit(ch);ch=getchar())x=x*10+ch-‘0‘;return x*f; 8 } 9 10 const double eps = 1e-4;11 const int N = 1010;12 struct Edge{13 ????int u,v;14 ????double w;15 ????Edge() {}16 ????Edge(int a,int b,double c) {u = a, v = b, w = c;} // -- double c17 ????bool operator < (const Edge &A) const {18 ????????return w < A.w;19 ????}20 }e[N*N];21 int x[N],y[N],fa[N],Enum,n,k;22 23 int find(int x) {24 ????if (x == fa[x]) return x;25 ????return fa[x] = find(fa[x]);26 }27 bool check(double x) {28 ????for (int i=1; i<=n; ++i) fa[i] = i;29 ????int cnt = 0;30 ????for (int i=1; i<=Enum; ++i) { // -- i<=n31 ????????if (e[i].w > x) break;32 ????????int u = find(e[i].u),v = find(e[i].v);33 ????????if (u != v) {34 ????????????fa[u] = v;35 ????????????cnt ++;36 ????????????if (cnt == n - 1) break;37 ????????}38 ????}39 ????if (n - cnt < k) return false; // 联通块的个数 40 ????return true;41 }42 int main() {43 ????n = read(),k = read();44 ????double L = 0,R = 0,mid,ans;45 ????for (int i=1; i<=n; ++i) 46 ????????x[i] = read(),y[i] = read();47 ????for (int i=1; i<=n; ++i) 48 ????????for (int j=i+1; j<=n; ++j) {49 ????????????double w = sqrt(1.0*(x[i]-x[j])*(x[i]-x[j])+1.0*(y[i]-y[j])*(y[i]-y[j]));50 ????????????e[++Enum] = Edge(i,j,w);51 ????????????R = max(R,w);52 ????????}53 ????sort(e+1,e+Enum+1);54 ????while (R - L >= eps) {55 ????????mid = (L + R) / 2.0;56 ????????if (check(mid)) ans = mid,L = mid; // -- L = mid + 1 57 ????????else R = mid; // -- R = mid - 158 ????}59 ????printf("%.2lf",ans);60 ????return 0;61 }另一种奇妙的写法。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 ?5 inline int read() { 6 ????int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch==‘-‘)f=-1; 7 ????for (;isdigit(ch);ch=getchar())x=x*10+ch-‘0‘;return x*f; 8 } 9 10 const int N = 1010;11 struct Edge{12 ????int u,v;double w;13 ????Edge() {}14 ????Edge(int a,int b,double c) {u = a, v = b, w = c;} // double c15 ????bool operator < (const Edge &A) const {16 ????????return w < A.w;17 ????}18 }e[N*N];19 int x[N],y[N],fa[N],Enum,n,k;20 21 int find(int x) {22 ????if (x == fa[x]) return x;23 ????return fa[x] = find(fa[x]);24 }25 int main() {26 ????n = read(),k = read();27 ????for (int i=1; i<=n; ++i) 28 ????????x[i] = read(),y[i] = read();29 ????for (int i=1; i<=n; ++i) 30 ????????for (int j=i+1; j<=n; ++j) {31 ????????????double w = sqrt(1.0*(x[i]-x[j])*(x[i]-x[j])+1.0*(y[i]-y[j])*(y[i]-y[j]));32 ????????????e[++Enum] = Edge(i,j,w);33 ????????}34 ????sort(e+1,e+Enum+1);35 ????for (int i=1; i<=n; ++i) fa[i] = i;36 ????int cnt = n;37 ????for (int i=1; i<=Enum; ++i) { // -- i<=n38 ????????int u = find(e[i].u), v = find(e[i].v);39 ????????if (u != v) { 40 ????????????fa[u] = v;41 ????????????cnt --;42 ????????}43 ????????if (cnt == k - 1) {printf("%.2lf",e[i].w);return 0;}44 ????}45 ????return 0;46 }1821: [JSOI2010]Group 部落划分 Group
原文地址：https://www.cnblogs.com/mjtcn/p/9279138.html