暑假集训Day15 D (数学最小生成树)

这题涉及到两个与Fibonacci数列有关的性质

一个是一定不存在两个Fibonacci数列项之和等于另外两个Fibonacci数列项所以最小生成树是唯一的，不存在多解的情况，这样让最大度最小这点可以忽略

另一个是假设a,b,c,d是四个Fibonacci数列项，如果a>b>(c,d)则对于任意c和d都有a+c>b+d，这点可以用来判断边权的大小

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 const int MAX=2e5+5;
 4 int n,m,fa[MAX],d[MAX],ans;
 5 struct Edge{
 6     int u,v;
 7 }ee[MAX];
 8 bool cmp(Edge x,Edge y){
 9     if (x.v==y.v) return x.u<y.u;
10     return x.v<y.v;
11 }
12 inline getfather(int x){return fa[x]==x?x:fa[x]=getfather(fa[x]);}
13 int main(){
14     freopen ("d.in","r",stdin);
15     freopen ("d.out","w",stdout);
16     int i,j,u,v,tx,ty;
17     scanf("%d%d",&n,&m);
18     for (i=1;i<=m;i++){
19         scanf("%d%d",&u,&v);
20         ee[i].u=min(u,v);
21         ee[i].v=max(u,v);
22     }
23     sort(ee+1,ee+m+1,cmp);
24     for (i=1;i<=n;i++) fa[i]=i;
25     for (i=1;i<=m;i++){
26         tx=getfather(ee[i].u);
27         ty=getfather(ee[i].v);
28         if (tx!=ty){
29             fa[tx]=ty;
30             d[ee[i].u]++,d[ee[i].v]++;
31         }
32     }ans=0;
33     for (i=1;i<=n;i++) ans=max(ans,d[i]);
34     printf("%d",ans);
35     return 0;
36 }

未来是什么样，未来会发生什么，谁也不知道。但是我知道，起码从今天开始努力，肯定比从明天开始努力，要快一天实现梦想。千里之行，始于足下！ ——《那年那兔那些事儿》

暑假集训Day15 D (数学 最小生成树)

暑假集训Day15 D (数学最小生成树)