杭電2015‘11校試合1007菜の花王国
5549 ワード
菜の花の王国
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1609 Accepted Submission(s): 411
Problem Description
プログラムデザインコンテストが間もなく到来し、学校ACM合宿チームの主力として、明ちゃんの訓練はずっと努力しています.今日は天気がよくて、コーチも気持ちがよくて、異例に選手たちに一日休みを取って、明ちゃんは自分の小さなロバに乗って郊外に足を踏み入れました.
町を出て間もなく、明ちゃんは大きな菜の花を見て、目の前の美しい景色の誘惑に耐えられず、曲がって入った.
菜の花王国には多くの菜の花精霊が生息しており、フィボナッチ数列を特に愛している生物である.この国には、いくつかの家族があり、どの精霊も一つの家族に属しています.精霊が生まれたとき、体にはコードが印刷されていて、この精霊の能力値を示しています.もしこの能力値がフィボナッチ数列にちょうど存在すれば、彼は所属する家族のために少し威信を高めます.明ちゃんは精霊たちと話をすることで、すべての精霊の関係を知った.
今、明ちゃんは菜の花王国で最も威信のある家族の威信値がどれだけあるか知りたいですが、助けてもらえますか.明ちゃんは精霊たちの関係ネットワークを教えてくれます.関係ネットワーク全体が膨大なので、明ちゃんはその中のいくつかの関係を繰り返し紹介する可能性があります.
Input
複数セットのデータを入力します.
各データの第1行は、菜の花王国の精霊の数と精霊との関係群数をそれぞれ表す2つの整数n(1<=n<=1000)、m(1<=m<=5000)を含む.2行目は、精霊たちの能力値k(1<=k<=10000000)を表すn個の整数を含む.次にm行があり、各行に2つの異なる整数u,v(1<=u,v<=n)があり、精霊uと精霊vが同じファミリーに属していることを示す.
Output
威望値が最大のファミリーの威望値を出力し、各グループのデータは1行に対応して出力してください.
Sample Input
2 1 1 4 1 2
Sample Output
1
問題:
テンプレートの問題を調べて....
コード#コード#
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1609 Accepted Submission(s): 411
Problem Description
プログラムデザインコンテストが間もなく到来し、学校ACM合宿チームの主力として、明ちゃんの訓練はずっと努力しています.今日は天気がよくて、コーチも気持ちがよくて、異例に選手たちに一日休みを取って、明ちゃんは自分の小さなロバに乗って郊外に足を踏み入れました.
町を出て間もなく、明ちゃんは大きな菜の花を見て、目の前の美しい景色の誘惑に耐えられず、曲がって入った.
菜の花王国には多くの菜の花精霊が生息しており、フィボナッチ数列を特に愛している生物である.この国には、いくつかの家族があり、どの精霊も一つの家族に属しています.精霊が生まれたとき、体にはコードが印刷されていて、この精霊の能力値を示しています.もしこの能力値がフィボナッチ数列にちょうど存在すれば、彼は所属する家族のために少し威信を高めます.明ちゃんは精霊たちと話をすることで、すべての精霊の関係を知った.
今、明ちゃんは菜の花王国で最も威信のある家族の威信値がどれだけあるか知りたいですが、助けてもらえますか.明ちゃんは精霊たちの関係ネットワークを教えてくれます.関係ネットワーク全体が膨大なので、明ちゃんはその中のいくつかの関係を繰り返し紹介する可能性があります.
Input
複数セットのデータを入力します.
各データの第1行は、菜の花王国の精霊の数と精霊との関係群数をそれぞれ表す2つの整数n(1<=n<=1000)、m(1<=m<=5000)を含む.2行目は、精霊たちの能力値k(1<=k<=10000000)を表すn個の整数を含む.次にm行があり、各行に2つの異なる整数u,v(1<=u,v<=n)があり、精霊uと精霊vが同じファミリーに属していることを示す.
Output
威望値が最大のファミリーの威望値を出力し、各グループのデータは1行に対応して出力してください.
Sample Input
2 1 1 4 1 2
Sample Output
1
問題:
テンプレートの問題を調べて....
コード#コード#
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<math.h>
#include<algorithm>
using namespace std;
int pre[1005];
int Find(int x)
{
int r=x;
while(r!=pre[r])
r=pre[r];
int i=x,j;
while(pre[i]!=r)
{
j=pre[i];
pre[i]=r;
i=j;
}
return r;
}
void mix(int x,int y)
{
int fx=Find(x),fy=Find(y);
if(fx!=fy)
{
pre[fy]=fx;
}
}
int power[1005];
long long a[71];
void init(void) {
a[0] = 0;
a[1] = a[2] = 1;
for (int i = 3; i <71; ++i) {
a[i] = a[i-1] + a[i-2];
}
}
int sum[1005];
int main()
{
int n,m;
init();
while (scanf("%d%d",&n,&m)!=EOF)
{
for (int i = 1;i<=n;i++)
{
scanf("%d",&power[i]);
pre[i]=i;
}
int c,d;
for (int i = 1;i<=m;i++)
{
scanf("%d%d",&c,&d);
mix(c,d);
}
for (int i = 1;i<=n;i++)
{
for (int j = 1;j<=45;j++)
if (power[i] == a[j])
{
sum[Find(i)]+=1;
break;
}
}
int maxn = 0;
for (int i = 1;i<=n;i++)
{
maxn = max(maxn,sum[i]);
}
printf("%d
",maxn);
memset(sum,0,sizeof(sum));
memset(power,0,sizeof(power));
memset(pre,0,sizeof(pre));
}
}