hdu 4786 Fibonacci Tree (最小、最大生成树)

题意：

N个点，M条边。每条边连接两个点u,v，且有一个权值c，c非零即一。

问能否将N个点形成一个生成树，并且这棵树的边权值和是一个fibonacii数。（fibonacii数=1,2,3,5,8 .... ）

思路：

若可以生成一棵树。则有最小生成树和最大生成树。假设已经生成了最小MST P 和最大MST Q。

将P更换一条边可以得到另一棵生成树，边权和不是和P相等就是比P的边权和大1。（因为边值非零即一）。同理搞下去....一定可以得到Q。

所以P的边权和到Q的边权和之间的所有值都能得到。故判断之间是否存在fibonacii数即可。

代码：

struct node{

    int u,v,c;

}edge[100005];

bool cmp(node a,node b){

    return a.c<b.c;

}

int fa[100005];

int T,n,m;

int findFa(int x){

    return fa[x]==x?x:fa[x]=findFa(fa[x]);

}

int kruskal1(){

    rep(i,1,n) fa[i]=i;

    int res=0;

    rep(i,1,m){

        int fx=findFa(edge[i].u);

        int fy=findFa(edge[i].v);

        if(fx!=fy){

            fa[fx]=fy;

            res+=edge[i].c;

        }

    }

    int tx=findFa(1);

    rep(i,2,n) if(findFa(i)!=tx) return -1;

    return res;

}

int kruskal2(){

    rep(i,1,n) fa[i]=i;

    int res=0;

    rep2(i,m,1){

        int fx=findFa(edge[i].u);

        int fy=findFa(edge[i].v);

        if(fx!=fy){

            fa[fx]=fy;

            res+=edge[i].c;

        }

    }

    int tx=findFa(1);

    rep(i,2,n) if(findFa(i)!=tx) return -1;

    return res;

}

bool isFibo[100005];

void FiboD(){

    mem(isFibo,false);

    int a=1,b=2; isFibo[1]=isFibo[2]=true;

    for(;;){

        int t=a+b;

        a=b, b=t;

        if(t>100000) break;

        isFibo[t]=true;

    }

}

int main(){

    //freopen("test.in","r",stdin);

    cin>>T;

    FiboD();

    rep(t,1,T){

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

        rep(i,1,m)

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

        sort(edge+1,edge+1+m,cmp);

        int mins=kruskal1();

        int maxs=kruskal2();

        printf("Case #%d: ",t);

        if(mins==-1 || maxs==-1) puts("No");

        else{

            bool flag=false;

            rep(i,mins,maxs) if(isFibo[i]){

                flag=true;

                break;

            }

            if(flag) puts("Yes"); else puts("No");

        }

    }

    //fclose(stdin);

}

巴特西

hdu 4786 Fibonacci Tree (最小、最大生成树)

最新文章

热门文章