1007 油菜花王國

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others) Problem Description 程序設計競賽即將到來，作為學校ACM集訓隊主力，小明訓練一直很努力。今天天氣不錯，教練也心情大好，破例給各位隊員放假一天，小明就騎著自己的小電驢到郊外踏青去了。

??出城不久，小明看到一大片油菜花，忍不住眼前美景的誘惑，就拐了進去，誰曾想，這一拐卻誤入了油菜花王國！

??油菜花王國生存著一大批油菜花精靈，這是一種特別熱愛斐波那契數列的生物。在這個國度里，有若干個家族，每只精靈都只屬于一個家族。精靈出生時，身上都會印著一個編碼，表示這只精靈的能力值，如果這個能力值正好存在于斐波那契數列，那么他就會為所在的家族增加一點威望。小明通過和精靈們聊天，知道了所有精靈之間的關系。

??現在，小明想知道油菜花王國里威望值最大的家族的威望值是多少，你能幫幫他嗎？小明會把精靈們之間的關系網絡告訴你，由于整個關系網絡實在太龐大，所以小明很有可能重復介紹其中一些關系。
Input 輸入包含多組數據。

每組數據第一行包含兩個整數 n (1 <= n <= 1000) 、 m (1 <= m <= 5000) ，分別表示油菜花王國精靈數量和精靈之間關系組數。
第二行包含 n 個整數，表示精靈們的能力值 k (1 <= k <= 1000000000)。
接下去有 m 行，每行有兩個不同的整數 u 、 v (1 <= u, v <= n) ，表示精靈 u 和精靈 v 屬于同一個家族。

Output 請輸出威望值最大的家族的威望值，每組數據對應一行輸出。
Sample Input 2 1 1 4 1 2
Sample Output 1 #include<stdio.h> #include<string.h> #include<stdlib.h> #include<stack> #include<math.h> #include<algorithm> #include<iostream> #define exp 1e-10 using namespace std; const int N = 1005; const int M = 1005; const int inf = 1000000007; const int mod = 2009; int s[N],a[N],c[N],ans[N]; int fun(int x) {if(c[x]!=x)c[x]=fun(c[x]);return c[x]; } int main() {int i,n,m,u,v,k,x,Max,p;s[0]=1;s[1]=1;for(i=2;; i++){s[i]=s[i-1]+s[i-2];if(s[i]>1000000000)break;}p=i;while(~scanf("%d%d",&n,&m)){memset(ans,0,sizeof(ans));for(i=1; i<=n; i++)c[i]=i;for(i=1; i<=n; i++)scanf("%d",&a[i]);for(i=0; i<m; i++){scanf("%d%d",&u,&v);c[fun(u)]=fun(v);}for(i=1; i<=n; i++){k=fun(i);x=lower_bound(s,s+p,a[i])-s;if(s[x]==a[i])ans[k]++;}for(Max=0,i=1; i<=n; i++)Max=max(Max,ans[i]);printf("%d\n",Max);}return 0; }
總是望著曾經的空間發呆，那些說好不分開的朋友不在了，轉身，陌路。 熟悉的，安靜了， 安靜的，離開了， 離開的，陌生了， 陌生的，消失了， 消失的，陌路了。

轉載于:https://www.cnblogs.com/im0qianqian/p/5989686.html

總結

以上是生活随笔為你收集整理的计算机学院大学生程序设计竞赛（2015’11）1007 油菜花王国的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。