LA 6540 Fibonacci Tree

以前做过的题···重新做一遍之后怎么做怎么wa···后来GG了···第二天看不知道为啥A了···难道我失忆了？

题意：无向图，边有黑色和白色两种颜色，求是否存在一个生成树中白边的个数是斐波那契数。

解法：并查集。对边按颜色进行排序，白边在前用并查集计算生成树中白边个数，再倒着算一遍，得到生成树的白边的最大值和最小值，判断其中有没有斐波那契数，注意要判断是否能构成生成树。

代码：

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<string>

#include<string.h>

#include<math.h>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#define LL long long

using namespace std;

int father[100005], f[100010] = {0};

struct node

{

    int u, v, c;

} edge[100005];

bool cmp(node a, node b)

{

    return a.c > b.c;

}

int FIND(int a)

{

    if(father[a] != a)

        father[a] = FIND(father[a]);

    return father[a];

}

int main()

{

    f[1] = 1;

    int f1 = 1, f2 = 1, f3 = 2;

    while(f3 < 100010)

    {

        f[f3] = 1;

        f1 = f2;

        f2 = f3;

        f3 = f1 + f2;

    }//斐波那契数打表

    int T;

    while(~scanf("%d", &T))

    {

        int cse = 1;

        while(T--)

        {

            int n, m, ans = 1;

            scanf("%d%d", &n, &m);

            for(int i = 0; i < m; i++)

                scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].c);

            sort(edge, edge + m, cmp);

            int l = 0, r = 0;

            for(int i = 0; i <= n; i++)

                father[i] = i;

            for(int i = 0; i < m; i++)

            {

                int a, b;

                a = FIND(edge[i].u);

                b = FIND(edge[i].v);

                if(a != b)

                {

                    r += edge[i].c;

                    father[a] = b;

                }

            }//计算白边最大值r

            int flag = FIND(1);

            for(int i = 2; i <= n; i++)

                if(FIND(i) != flag)

                {

                    ans = 0;

                    break;

                }//判断是否有生成树

            if(ans)

            {

                ans = 0;

                for(int i = 0; i <= n; i++)

                    father[i] = i;

                for(int i = m-1; i >= 0; i--)

                {

                    int a, b;

                    a = FIND(edge[i].u);

                    b = FIND(edge[i].v);

                    if(a != b)

                    {

                        l += edge[i].c;

                        father[a] = b;

                    }

                }//计算白边最小值l

                for(int i = l; i <= r; i++)

                    if(f[i])

                    {

                        ans = 1;

                        break;

                    }

            }

            if(ans)

                cout << "Case #" << cse++ << ": Yes" << endl;

            else

                cout << "Case #" << cse++ << ": No" << endl;

        }

    }

    return 0;

}

最近想改变一下代码风格···结果连字都快不会打了orz