HDU 4786

本文主要是介绍HDU 4786，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

      很好的一道题目，考验人的解决问题的思路。如果你想直接解出这道题的答案，感觉会无从下手，但是如果你只是求出一个可能包含答案的区间，然后在区间内搜索，那么解决起来就简单了。

      我们可以按照把1和0分别当做黑边和白边的权值，求出最大生成树和最小生成树。其中，最大生成树中白边的数量代表所有生成树中白边最少需要多少条，最小生成树代表白边最多有多少条。如果这个区间内包含斐波那契数，则说明存在符合题意的斐波那契树，否则就不存在。

     此外，还要注意图的连通性。不连通的图是不存在生成树的，也就是没答案的。

代码（C++）：

#include <iostream>
#include <cstdio>
#include <algorithm>#define MAX 100009
using namespace std;struct Edge{int a;int b;int w;
} edge[MAX];int c,fib[25],pre[MAX],num;void add_edge(int a,int b,int w)
{edge[c].a=a;edge[c].b=b;edge[c].w=w;c++;
}bool cmp1(Edge x,Edge y)
{if(x.w!=y.w) return x.w<y.w;if(x.a!=y.a) return x.a<y.a;return x.b<y.b;
}bool cmp2(Edge x,Edge y)
{if(x.w!=y.w) return x.w>y.w;if(x.a!=y.a) return x.a>y.a;return x.b>y.b;
}int find(int v)
{if(pre[v]!=v) pre[v]=find(pre[v]);return pre[v];
}void merge(int a,int b)
{pre[a]=b;
}int kruskal(int n)
{int i,count,pre_a,pre_b,a,b;count=num=0;for(i=1;i<=n;i++) pre[i]=i;for(i=0;i<c;i++){a=edge[i].a;b=edge[i].b;pre_a=find(a);pre_b=find(b);if(pre_a!=pre_b){merge(pre_a,pre_b);if(edge[i].w==1) count++;num++;}if(num==n-1) break;}return count;
}int main()
{//freopen("in.txt","r",stdin);int t,n,m,a,b,w,i,k,num1,num2;fib[0]=1;fib[1]=2;for(i=2;i<25;i++){fib[i]=fib[i-1]+fib[i-2];}scanf("%d",&t);for(k=1;k<=t;k++){scanf("%d %d",&n,&m);c=0;for(i=0;i<m;i++){scanf("%d %d %d",&a,&b,&w);add_edge(a,b,w);}sort(edge,edge+c,cmp1);num1=kruskal(n);//如果图不连通，则直接输出"No"if(num<n-1){printf("Case #%d: No\n",k);continue;}sort(edge,edge+c,cmp2);num2=kruskal(n);for(i=0;i<25;i++){if(fib[i]>=num1&&fib[i]<=num2) break;}if(i==25) printf("Case #%d: No\n",k);else printf("Case #%d: Yes\n",k);}return 0;
}

Fibonacci Tree

  
2
4 4
1 2 1
2 3 1
3 4 1
1 4 0
5 6
1 2 1
1 3 1
1 4 1
1 5 1
3 5 1
4 2 1

  
Case #1: Yes
Case #2: No

这篇关于HDU 4786的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！