一个由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在这里实在是。。。唉