hdoj 4786 Fibonacci Tree

Fibonacci Tree

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 3583    Accepted Submission(s): 1152

Problem 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, ... )  

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).  

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 表示黑線連接配接！
  
  
                圖要連通，但所構成圖的白色線個數必須符合是屬于fib序列！并不需要所有的線全都是白線！
  
  
       思路：    
  
  
                可以根據線條的顔色，先盡量用白色線條進行圖的連通，求出滿足連通時白色線條的條數max ，相反，盡量用黑色線條，求出
  
  
                此時滿足連通的白色線條的個數min，再min和max之間尋找是否有fib滿足數列的數！
  
  

  
  
        具體看代碼：
  
            
          
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define  N  110000
int set[N],n,m;
int fib[1000000+2100];
struct node
{
	int start;
	int end;
	int judge;
}num[N];
bool cmp1(node a,node  b)//按照先黑再白順序 
{
	return  a.judge <b.judge;
}
bool cmp2(node a,node  b)//順序與前面相反 
{
	return  a.judge>b.judge;
}
void  dabiao()
{
	  fib[1]=1;fib[2]=2;
	for(int  i=3;i<1000000+100;i++)
	{
		fib[i]=fib[i-1]+fib[i-2];
	}
}
int find(int  p)//找根節點 
{
	int t;
	int child=p;
	while(p!=set[p])
	p=set[p];
	while(child!=p)
	{
		t=set[child];
		set[child]=p;
		child=t;
	}
	return  p;
}
void merge(int x,int y)//加入集合 
{
	int  fx=find(x);
	int fy=find(y);
	if(fx!=fy)
	set[fx]=fy;
}
int main()
{
	int  t,k=1;
	memset(fib,0,sizeof(fib));
	dabiao();
	scanf("%d",&t);
	while(t--)
	{
		int i,j,n,m,max=0,min=0;
		scanf("%d%d",&n,&m);
		for(i=1;i<=m;i++)
		scanf("%d%d%d",&num[i].start ,&num[i].end ,&num[i].judge );
		for(i=1;i<=n;i++)
	    set[i]=i;
		sort(num+1,num+m,cmp2); //盡量先用白色線條！ 
		for(i=1;i<=m;i++)
		{
			if(find(num[i].start )!=find(num[i].end ))
			{
				merge(num[i].start ,num[i].end );
				if(num[i].judge )
				 max++;
			}
		} 
		for(i=1;i<=n;i++)
	    set[i]=i;
		sort(num+1,num+m,cmp1);//盡量先用黑色線條！ 
		for(i=1;i<=m;i++)
		{
			if(find(num[i].start )!=find(num[i].end))
			{
				merge(num[i].start ,num[i].end );
				if(num[i].judge )
				min++;
			}
		}	 
		printf("Case #%d: ",k++);
		int exit=0;
		for(i=1;i<=n;i++)//看是否連通！ 
		{
			if(set[i]==i)
			 exit++;
			 if(exit>1)
			 break;
		}
		if(exit>1)
		{
			printf("No\n");
			continue;
		}
		exit=0;
		for(i=1;fib[i]<=max;i++)
		{
			if(fib[i]>=min&&fib[i]<=max)
			{
				exit++;
			}
			if(exit)
			break;
		}
		if(exit)
		printf("Yes\n");
		else
		printf("No\n");
	}
	return  0;
}