【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数在区间内就可以了。

  1 #include <cstdio>
  2 #include <algorithm>
  3 using namespace std;
  4 const int MAX_N=100005;
  5 const int MAX_M=100005;
  6 int T;
  7 int n,m;
  8 struct Edge
  9 {
 10     int from,to,cost;
 11 }edges[MAX_M];
 12
 13 bool cmp0(const Edge e1,const Edge e2)
 14 {return e1.cost<e2.cost;}
 15 bool cmp1(const Edge e1,const Edge e2)
 16 {return e1.cost>e2.cost;}
 17
 18 int parent[MAX_N];
 19 int rankk[MAX_N];
 20 void init(int N)
 21 {
 22     for(int i=0;i<=N;i++)
 23     {
 24         parent[i]=i;
 25         rankk[i]=0;
 26     }
 27 }
 28 int find(int x)
 29 {
 30     if(parent[x]==x) return x;
 31     return parent[x]=find(parent[x]);
 32 }
 33 void unite(int x,int y)
 34 {
 35     x=find(x);
 36     y=find(y);
 37     if(x==y) return;
 38     if(rankk[x]<rankk[y]) parent[x]=y;
 39     else
 40     {
 41         parent[y]=x;
 42         if(rankk[x]==rankk[y]) rankk[x]++;
 43     }
 44 }
 45 bool same(int x,int y)
 46 {return find(x)==find(y);}
 47
 48 int kruscal()
 49 {
 50     int ans=0;
 51     init(n);
 52     for(int i=0;i<m;i++)
 53     {
 54         if(!same(edges[i].from,edges[i].to))
 55         {
 56             unite(edges[i].from,edges[i].to);
 57             ans+=edges[i].cost;
 58         }
 59     }
 60     return ans;
 61 }
 62
 63 int fib[25];
 64 void init_fib()
 65 {
 66     fib[0]=fib[1]=1;
 67     for(int i=2;fib[i-1]<MAX_M;i++)
 68         fib[i]=fib[i-1]+fib[i-2];
 69 /*
 70     for(int i=0;fib[i]<MAX_M;i++)
 71         printf("%d %d\n",i,fib[i]);
 72     printf("\n");
 73 */
 74 }
 75
 76 int main()
 77 {
 78     init_fib();
 79     freopen("4786.txt","r",stdin);
 80     scanf("%d",&T);
 81     for(int ca=1;ca<=T;ca++)
 82     {
 83         scanf("%d%d",&n,&m);
 84         for(int i=0;i<m;i++)
 85             scanf("%d%d%d",&edges[i].from,&edges[i].to,&edges[i].cost);
 86         printf("Case #%d: ",ca);
 87         if(n==1||m==0||m<n-1)//所给边数<n-1一定不连通
 88         {
 89             printf("No\n");
 90             continue;
 91         }
 92         sort(edges,edges+m,cmp0);
 93         int left=kruscal();
 94         sort(edges,edges+m,cmp1);
 95         int right=kruscal();
 96
 97         int flag=1;
 98         for(int i=2;i<=n;i++)//判是否为连通图（重边不影响求MST，但不能仅凭所给边数m判是否连通）
 99             if(!same(1,i)){flag=0; break;}
100         if(!flag)
101             {printf("No\n"); continue;}
102
103         flag=0;
104         for(int i=0;i<25;i++)//枚举100000以内的fibonacci数，有进入范围的即可
105             if(left<=fib[i]&&fib[i]<=right)
106                 {flag=1;break;}
107         if(flag) printf("Yes\n");
108         else printf("No\n");
109     }
110     return 0;
111 }

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

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

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

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

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