题目描述
一共$n$个点$m$条边,每条边有个权值$1$代表白边,$0$代表黑边,求能否建一个生成树,使得白边的数量是一个斐波那契数列
输入样例
2
4 4
1 2 1
2 3 1
3 4 1
1 4 0
5 6
1 2 1
1 3 1
1 4 1
1 5 1
3 5 1
4 2 1
输出样例
Case #1: Yes
Case #2: No
(MST MBT,结论) $O(nlogn)$
首先考虑极端情况,求出来构成生成树的最小白边数量$minn$和最大白边数量$maxx$,即求最小生成树和最大生成树。那么找这个区间内有没有斐波那契数即可。关键在于如何证明$minn$~$maxx$之间的所有情况都可以被构造出来。
结论:只有0和1两种权值的图中,$MST$~$MBT$内的任意权值的生成树都可以被构造出来。
可以理解为:
白色边权为$1$,黑色边权为$0$,已知最小生成树为$minn$,最大生成树为$maxx$,那么我们一定可以通过$+1$(黑边换为白边),$-1$(白边换为黑边)的方式在不改变生成树性质的前提下将$minn$转移到$maxx$,所以这其中的任何一个权值都可以被凑出来。
具体证明: hdu 4786 Fibonacci Tree
注意不连通的情况。
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n,m;
int f[N],fb[N];
struct Edge
{
int a,b,w;
}e[N];
int t;
bool st[N*2];
bool cmp1(Edge a,Edge b)
{
return a.w>b.w;
}
bool cmp2(Edge a,Edge b)
{
return a.w<b.w;
}
int get(int x)
{
if(x!=f[x])
f[x]=get(f[x]);
return f[x];
}
int kruskal()
{
for(int i=1;i<=n;i++) f[i]=i;
int cnt=0;
int sum=0;
for(int i=1;i<=m;i++)
{
int a,b,w;
a=e[i].a,b=e[i].b,w=e[i].w;
int fa,fb;
fa=get(a),fb=get(b);
if(fa!=fb)
{
f[fa]=fb;
cnt++;
sum+=w;
}
if(cnt==n-1) break;
}
if(cnt==n-1) return sum;
return -1;
}
int main()
{
int cnt=3;
fb[1]=1,fb[2]=2;
st[1]=st[2]=1;
while(fb[cnt-1]<N+10)
{
fb[cnt]=fb[cnt-1]+fb[cnt-2];
st[fb[cnt]]=1;
cnt++;
}
cin>>t;
for(int j=1;j<=t;j++)
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b,w;
cin>>a>>b>>w;
e[i]={a,b,w};
}
int minn,maxx;
sort(e+1,e+m+1,cmp1);
maxx=kruskal();
sort(e+1,e+m+1,cmp2);
minn=kruskal();
printf("Case #%d: ",j);
// cout<<minn<<" "<<maxx<<endl;
int flag=1;
if(maxx==-1||minn==-1) cout<<"No"<<endl;
else
{
for(int i=minn;i<=maxx;i++)
{
if(st[i])
{
cout<<"Yes"<<endl;
flag=0;
break;
}
}
if(flag)
cout<<"No"<<endl;
}
}
return 0;
}