每日一题 day39 打卡
Analysis
1.当正向思考受阻时，逆向思维可能有奇效。
2.问题转化为：找到最小的d，使去掉所有权值>d的边之后，连通支的个数<k;
3.定理：如果去掉所有权值>d的边之后，最小生成树被分割为k个连通支，则图也被分为k个连通支。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define maxn 10000000+10 7 #define INF 9187201950435737471 8 #define rep(i,s,e) for(register int i=s;i<=e;++i) 9 #define dwn(i,s,e) for(register int i=s;i>=e;--i) 10 using namespace std; 11 inline int read() 12 { 13 int x=0; 14 bool f=1; 15 char c=getchar(); 16 for(; !isdigit(c); c=getchar()) if(c=='-') f=0; 17 for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0'; 18 if(f) return x; 19 return 0-x; 20 } 21 inline void write(int x) 22 { 23 if(x<0){putchar('-');x=-x;} 24 if(x>9)write(x/10); 25 putchar(x%10+'0'); 26 } 27 int n,k,cnt,tot; 28 int f[maxn]; 29 double ans[maxn]; 30 struct node1 31 { 32 int x,y; 33 }coo[maxn]; 34 struct node2 35 { 36 int xx,yy; 37 double dis; 38 }tree[maxn]; 39 inline double calc(int x_,int y_,int x__,int y__) 40 { 41 return sqrt(((double)x_-(double)x__)*((double)x_-(double)x__)+((double)y_-(double)y__)*((double)y_-(double)y__)); 42 } 43 inline int find(int x) 44 { 45 if(f[x]==x) return x; 46 return f[x]=find(f[x]); 47 } 48 bool cmp(node2 x,node2 y) 49 { 50 return x.dis<y.dis; 51 } 52 signed main() 53 { 54 rep(i,1,1000) f[i]=i; 55 n=read();k=read(); 56 rep(i,1,n) coo[i].x=read(),coo[i].y=read(); 57 rep(i,1,n) 58 rep(j,i+1,n) 59 { 60 tree[++cnt].xx=i; 61 tree[cnt].yy=j; 62 tree[cnt].dis=calc(coo[i].x,coo[i].y,coo[j].x,coo[j].y); 63 } 64 sort(tree+1,tree+cnt+1,cmp); 65 rep(i,1,cnt) 66 { 67 int f1=find(tree[i].xx); 68 int f2=find(tree[i].yy); 69 if(f1!=f2) 70 { 71 f[f1]=f2; 72 ans[++tot]=tree[i].dis; 73 if(tot==n-1) break; 74 } 75 } 76 printf("%.2lf",ans[tot-k+1]); 77 return 0; 78 }
请各位大佬斧正