题目传送门


题意：给你一个图，图中边颜色为白色（1表示）或者黑色（0表示），问你是否能找出一棵树，使这棵树中白边的总数量的值为Fib数。点数n和变数m均为不大于1e5的数。

分析：这是最小生成树的变形题，用Kruskal求解，我们可以通过求两次最小生成树得到白边数量的上下限，再判断这个区间内有没有fib数即可，第一次我们以黑边为主排序求最小生成树，得到白边数量下限，再以白边为主排序求最小生成树得到白边数量上限。注意如果一开始图不连通，那么输出No。


ac代码如下

#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<iostream>
#include<algorithm>
using namespace std;

bool fib[100010];
int fa[100010];
struct node{
   int st,en,len;
}E[100010];
int n,m;

int Find(int x)
{
    if(x==fa[x])
        return x;
    else
        return fa[x]=Find(fa[x]);
}

void init()
{
    memset(fib,false,sizeof(fib));
    int a=1,b=2,c;
    fib[a]=fib[b]=true;
    while(c<=100000)
    {
        c=a+b;
        fib[c]=true;
        a=b;
        b=c;
    }
}

bool cmp1(const node &a,const node &b)
{
    return a.len<b.len;
}
bool cmp2(const node &a,const node &b)
{
    return a.len>b.len;
}

int main()
{
    int tt,ncase=1;
    scanf("%d",&tt);
    init();
    while(tt--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&E[i].st,&E[i].en,&E[i].len);
        }
        int ans1=0,ans2=0;
        sort(E+1,E+m+1,cmp1);
        for(int i=1;i<=n;i++)
        {
            fa[i]=i;
        }
        for(int i=1;i<=m;i++)
        {
            int fx=Find(E[i].st);
            int fy=Find(E[i].en);
            if(fx!=fy)
            {
                ans1+=E[i].len;
                fa[fx]=fy;
            }
        }
        bool ok=true;
        int tmp=Find(1);
        for(int i=2;i<=n;i++)
        {
            if(Find(i)!=tmp)ok=false;
        }
        if(!ok)
        {
            printf("Case #%d: No\n",ncase++);
            continue;
        }
        sort(E+1,E+m+1,cmp2);
        for(int i=1;i<=n;i++)
        {
            fa[i]=i;
        }
        for(int i=1;i<=m;i++)
        {
            int fx=Find(E[i].st);
            int fy=Find(E[i].en);
            if(fx!=fy)
            {
                ans2+=E[i].len;
                fa[fx]=fy;
            }
        }
        bool flag=false;
        for(int i=ans1;i<=ans2;i++)
        {
            if(fib[i])
            {
                flag=true;
                break;
            }
        }
        if(flag)
            printf("Case #%d: Yes\n",ncase++);
        else
            printf("Case #%d: No\n",ncase++);
    }
    return 0;
}