hdu4786Fibonacci Tree【kruskal最小生成树】
Description
Coach Pang is interested in Fibonacci numbers while Uncle Yang wants him to do some research on Spanning Tree. So Coach Pang decides to solve the following problem:
Consider a bidirectional graph G with N vertices and M edges. All edges are painted into either white or black. Can we find a Spanning Tree with some positive Fibonacci number of white edges?
(Fibonacci number is defined as 1, 2, 3, 5, 8, ... )
Consider a bidirectional graph G with N vertices and M edges. All edges are painted into either white or black. Can we find a Spanning Tree with some positive Fibonacci number of white edges?
(Fibonacci number is defined as 1, 2, 3, 5, 8, ... )
Input
The first line of the input contains an integer T, the number of test cases.
For each test case, the first line contains two integers N(1 <= N <= 10 5) and M(0 <= M <= 10 5).
Then M lines follow, each contains three integers u, v (1 <= u,v <= N, u<> v) and c (0 <= c <= 1), indicating an edge between u and v with a color c (1 for white and 0 for black).
For each test case, the first line contains two integers N(1 <= N <= 10 5) and M(0 <= M <= 10 5).
Then M lines follow, each contains three integers u, v (1 <= u,v <= N, u<> v) and c (0 <= c <= 1), indicating an edge between u and v with a color c (1 for white and 0 for black).
Output
For each test case, output a line “Case #x: s”. x is the case number and s is either “Yes” or “No” (without quotes) representing the answer to the problem.
Sample Input
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
Sample Output
Case #1: Yes Case #2: No
给定无向图每个边要么是白色，要么是黑色。求生成树的白边个数能否是斐波那契数。其实应该能想到的，让白边是1，黑边是0，求最大生成树和最小生成树。看中间范围是否有斐波那契数。注意是无向图，加边加两个！kruskal返回-1就是不连通呀，没必要拿并查集来判断~
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005;
const int maxm=200005;
int F[maxn];
struct Edge
{
int u,v,w;
}edge[maxm];
int tol;
void addedge(int u,int v,int w)
{
edge[tol].v=v;
edge[tol].u=u;
edge[tol++].w=w;
}
bool cmp(Edge a,Edge b)
{
return a.w<b.w;
}
bool cmp2(Edge a,Edge b)
{
return a.w>b.w;
}
int fnd(int x)
{
return x==F[x]?x:F[x]=fnd(F[x]);
}
int kruskal(int n)
{
for(int i=1;i<=n;i++) F[i]=i;
// sort(edge,edge+tol,cmp);
int cnt=0;
int ans=0;
for(int i=0;i<tol;i++)
{
int u=edge[i].u;
int v=edge[i].v;
int w=edge[i].w;
int a=fnd(u);
int b=fnd(v);
if(a!=b)
{
ans+=w;
F[b]=a;
cnt++;
}
if(cnt==n-1)break;
}
if(cnt<n-1)return -1;
return ans;
}
int num[100],cnt;
void init()
{
num[0]=0;num[1]=1;num[2]=2;num[3]=3;
cnt=4;
while(num[cnt-1]<=100005)
{
num[cnt]=num[cnt-1]+num[cnt-2];
cnt++;
// cout<<num[cnt-1]<<endl;
}
}
int main()
{
//freopen("cin.txt","r",stdin);
int t,n,m,cas=1;
scanf("%d",&t);
init();
while(t--)
{
scanf("%d%d",&n,&m);
tol=0;
while(m--)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);///!!!
}
printf("Case #%d: ",cas++);
sort(edge,edge+tol,cmp);
int small=kruskal(n);
bool ff=true;
sort(edge,edge+tol,cmp2);
int big=kruskal(n);
// printf("s=%d,b=%d\n",small,big);
if(small==-1||big==-1)
{
puts("No");
continue;
}
bool flag=false;
for(int i=1;i<=23;i++)
{
if(num[i]>=small&&num[i]<=big)
{
flag=true;
break;
}
}
if(flag) printf("Yes\n");
else printf("No\n");
}
return 0;
}
投递快手等公司10个岗位