【HDU 4786 Fibonacci Tree】最小生成树

一个由n个顶点m条边（可能有重边）构成的无向图（可能不连通），每条边的权值不是0就是1。

给出n、m和每条边的权值，问是否存在生成树，其边权值和为fibonacci数集合{1，2，3，5，8...}中的一个。

求最小生成树和最大生成树，得到生成树边权和的下界left和上界right。这道题由于每条边权值不是0就是1，因此生成树边权和可以覆盖到[left,right]的每一个数。那么求得[left,right]，看是否有fibonacci数在区间内就可以了。

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 const int MAX_N=;

 const int MAX_M=;

 int T;

 int n,m;

 struct Edge

 {

     int from,to,cost;

 }edges[MAX_M];

 bool cmp0(const Edge e1,const Edge e2)

 {return e1.cost<e2.cost;}

 bool cmp1(const Edge e1,const Edge e2)

 {return e1.cost>e2.cost;}

 int parent[MAX_N];

 int rankk[MAX_N];

 void init(int N)

 {

     for(int i=;i<=N;i++)

     {

         parent[i]=i;

         rankk[i]=;

     }

 }

 int find(int x)

 {

     if(parent[x]==x) return x;

     return parent[x]=find(parent[x]);

 }

 void unite(int x,int y)

 {

     x=find(x);

     y=find(y);

     if(x==y) return;

     if(rankk[x]<rankk[y]) parent[x]=y;

     else

     {

         parent[y]=x;

         if(rankk[x]==rankk[y]) rankk[x]++;

     }

 }

 bool same(int x,int y)

 {return find(x)==find(y);}

 int kruscal()

 {

     int ans=;

     init(n);

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

     {

         if(!same(edges[i].from,edges[i].to))

         {

             unite(edges[i].from,edges[i].to);

             ans+=edges[i].cost;

         }

     }

     return ans;

 }

 int fib[];

 void init_fib()

 {

     fib[]=fib[]=;

     for(int i=;fib[i-]<MAX_M;i++)

         fib[i]=fib[i-]+fib[i-];

 /*

     for(int i=0;fib[i]<MAX_M;i++)

         printf("%d %d\n",i,fib[i]);

     printf("\n");

 */

 }

 int main()

 {

     init_fib();

     freopen("4786.txt","r",stdin);

     scanf("%d",&T);

     for(int ca=;ca<=T;ca++)

     {

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

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

             scanf("%d%d%d",&edges[i].from,&edges[i].to,&edges[i].cost);

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

         if(n==||m==||m<n-)//所给边数<n-1一定不连通

         {

             printf("No\n");

             continue;

         }

         sort(edges,edges+m,cmp0);

         int left=kruscal();

         sort(edges,edges+m,cmp1);

         int right=kruscal();

         int flag=;

         for(int i=;i<=n;i++)//判是否为连通图（重边不影响求MST，但不能仅凭所给边数m判是否连通）

             if(!same(,i)){flag=; break;}

         if(!flag)

             {printf("No\n"); continue;}

         flag=;

         for(int i=;i<;i++)//枚举100000以内的fibonacci数，有进入范围的即可

             if(left<=fib[i]&&fib[i]<=right)

                 {flag=;break;}

         if(flag) printf("Yes\n");

         else printf("No\n");

     }

     return ;

 }

开始觉得可以按一种贪心策略求得一个最优解，如果命中不了fibonacci数则无解。

想贪心的先选权值为0的边，画图发现可能错过fibonacci数，贪心的先选权值为1的边依然可能错过。

画各种例子，发现割边是必须取的，因此边权和有个下界。去掉割边后剩下的就是圈了，每个圈去掉一条边即得生成树；想枚举每个圈的所有情况看能不能命中fibonacci数，但并是不会实现，尤其对很复杂的图。

队友提出过求出上下界然后看是否有fibonacci数在之间，无奈我开始没听懂。。。

另，用m>=n-1判连通的话，m是去掉重边后的边数，WA在这里实在是。。。唉

巴特西

【HDU 4786 Fibonacci Tree】最小生成树

最新文章

热门文章