hdu 4786 最小生成树与最大生成树

/*

  题意 ：有一些边权值为1和0，判断是否存在一个生成树使得他的总权值为一个斐波那契数。

  解法：建立一个最小生成树向里面加权值为1的边替换为0的边，保证原来的联通。因为权值为1，可直接求出最大生成树和最小生成树。

  判断他们中间是否有斐波那契数即可，当然要先判断是否可以构成一个生成树。

  这个我刚开始忘判断了。

*/

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#define N 110000

struct node

{

    int u,v,w;

} bian[N];

int f[N*2],flag[N*2],pre[N];

int cmp(const void *a,const void *b)

{

    return (*(struct node *)a).w-(*(struct node *)b).w;

}

int find(int x)

{

    if(x!=pre[x])

        pre[x]=find(pre[x]);

    return pre[x];

}

int cmpp(const void *a,const void *b)

{

    return (*(struct node *)b).w-(*(struct node *)a).w;

}

int main()

{

    int t,m,n,i,j=0,k,suma,sumb,d;

    memset(flag,0,sizeof(flag));

    f[0]=1;

    f[1]=1;

    flag[1]=1;

    for(i=2; i<=25; i++)

    {

        f[i]=f[i-1]+f[i-2];

        flag[f[i]]=1;

       // printf("%d ",f[i]);

    }

    scanf("%d",&t);

    while(t--)

    {

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

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

            scanf("%d%d%d",&bian[i].u,&bian[i].v,&bian[i].w);

        qsort(bian,m,sizeof(bian[0]),cmp);

        for(i=1; i<=n; i++)

            pre[i]=i;

        k=0;

        suma=0;

        for(i=0; i<m&&k<n-1; i++)

        {

            int u=find(bian[i].u);

            int v=find(bian[i].v);

            if(u!=v)

            {

                pre[u]=v;

                k++;

                suma+=bian[i].w;

            }

        }

        if(i==m&&k!=n-1) {//注意判断无法生成最小生成树的条件

             printf("Case #%d: No\n",++j);

             continue;

        }

        for(i=1; i<=n; i++)

            pre[i]=i;

        qsort(bian,m,sizeof(bian[0]),cmpp);

        k=0;

        sumb=0;

        for(i=0; i<m&&k<n-1; i++)

        {

            int u=find(bian[i].u);

            int v=find(bian[i].v);

            if(u!=v)

            {

                pre[u]=v;

                k++;

                sumb+=bian[i].w;

            }

        }

        d=0;

        for(i=suma; i<=sumb; i++)

            if(flag[i]){

                d=1;

            break;

            }

        if(d)

            printf("Case #%d: Yes\n",++j);

        else

            printf("Case #%d: No\n",++j);

    }

    return 0;

}
巴特西

hdu 4786 最小生成树与最大生成树

最新文章

热门文章
