Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7965 Accepted Submission(s): 2406
题目大意：
给定一堆权值为0或1的边，问是否能组成一棵生成树，使得生成树的边权值之和为斐波那契数列上的数
思路：
先用并查集判断是不是连通图，如果不是直接为No
边权值按从小到大的顺序排一遍，生成树求出最小值minn
边权值按从大到小的顺序排一遍，生成树求出最大值maxn
判断[minn,maxn]存不存在斐波那契数列上的数，存在Yes，不存在No（权值为1的边可以用多条权值为0的边去凑）
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 int t,n,m,ca=0; 6 const int MAX=1e5+5; 7 struct Edge{ 8 int from,to,val; 9 }edge[MAX]; 10 int fa[MAX],fib[MAX]; 11 12 void sol(){ 13 fib[1]=fib[2]=1; 14 int bef=1,nxt=2,sum=bef+nxt; 15 while(sum<MAX){ 16 fib[sum]=1; 17 bef=nxt; 18 nxt=sum; 19 sum=bef+nxt; 20 } 21 } 22 23 int find(int x){ 24 int k=x; 25 while(fa[k]!=k)k=fa[k]; 26 int w=x,ww; 27 while(fa[w]!=w){ 28 ww=fa[w]; 29 fa[w]=k; 30 w=ww; 31 } 32 return k; 33 } 34 35 bool cmp1(Edge x,Edge y){ 36 return x.val<y.val; 37 } 38 39 bool cmp2(Edge x,Edge y){ 40 return x.val>y.val; 41 } 42 43 int kruskal(){ 44 int res=0; 45 for(int i=1;i<=n;i++)fa[i]=i; 46 for(int i=0,k=0;i<m&&k<n-1;i++,k++){ 47 int fx=find(edge[i].from),fy=find(edge[i].to); 48 if(fx!=fy){ 49 fa[fx]=fy; 50 res+=edge[i].val; 51 } 52 } 53 return res; 54 } 55 56 int main(){ 57 sol(); 58 scanf("%d",&t); 59 while(t--){ 60 scanf("%d%d",&n,&m); 61 for(int i=1;i<=n;i++)fa[i]=i; 62 for(int i=0;i<m;i++){ 63 scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].val); 64 int fx=find(edge[i].from),fy=find(edge[i].to); 65 if(fx!=fy){ 66 fa[fx]=fy; 67 } 68 } 69 int flag=1; 70 int rt=find(1); 71 for(int i=1;i<=n;i++){ 72 if(find(i)!=rt){ 73 flag=0; 74 break; 75 } 76 } 77 if(flag==0){ 78 printf("Case #%d: No\n",++ca); 79 continue; 80 } 81 sort(edge,edge+m,cmp1); 82 int minn=kruskal(); 83 sort(edge,edge+m,cmp2); 84 int maxn=kruskal(); 85 flag=0; 86 for(int i=minn;i<=maxn;i++){ 87 if(fib[i]==1){ 88 flag=1; 89 break; 90 } 91 } 92 if(flag==1)printf("Case #%d: Yes\n",++ca); 93 else printf("Case #%d: No\n",++ca); 94 } 95 }
hdu4786 Fibonacci Tree（kruskal+并查集）
原文：https://www.cnblogs.com/ChangeG1824/p/11679955.html