Fibonacci Tree(最小最大生成树)
发布时间:2020-12-15 07:23:20 所属栏目:Java 来源:网络整理
导读:Fibonacci Tree Time Limit: 4000/2000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7969????Accepted Submission(s): 2409 Problem Description Coach Pang is interested in Fibonacci numbers while Uncle Yang
Fibonacci TreeTime Limit: 4000/2000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
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
?
解题思路: 白边最小生成树值low? 最大生成树high? ?中间的值生成树必定存在;
?
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 6 using namespace std; 7 int t,n,m,cnt; 8 const int N=1e5+5; 9 int arr[N]; 10 int brr[N]; 11 12 struct Node{ 13 int u,v,ee; 14 }A[N]; 15 16 int judge(){ 17 brr[1]=1,brr[2]=2; 18 for(int i=3;i<=31;i++){ 19 brr[i]=brr[i-1]+brr[i-2]; 20 } 21 } 22 23 int cmp1(Node a,Node b){ return a.ee<b.ee; } 24 int cmp2(Node a,Node b){ return a.ee>b.ee; } 25 26 int find_root(int x){ return arr[x]==x?x:arr[x]=find_root(arr[x]); } 27 void merge_unit(int x,int y){ 28 int xx=find_root(x); 29 int yy=find_root(y); 30 if(xx!=yy) arr[xx]=yy; 31 } 32 int kurscul(){ 33 cnt=0; 34 int num=0; 35 for(int i=1;i<=N-1;i++) arr[i]=i; 36 for(int i=1;i<=m;i++){ 37 if(find_root(A[i].u)!=find_root(A[i].v)){ 38 cnt++; 39 merge_unit(A[i].u,A[i].v); 40 num+=A[i].ee; 41 } 42 } 43 return num; 44 } 45 46 int main(){ 47 ios::sync_with_stdio(false); 48 judge(); 49 int jishu=0; 50 cin>>t; 51 while(t--){ 52 cin>>n>>m; 53 for(int i=1,d1,d2,d3;i<=m;i++){ 54 cin>>d1>>d2>>d3; 55 A[i]={d1,d3}; 56 } 57 sort(A+1,A+1+m,cmp1); 58 int low=kurscul(); 59 cout << "Case #" << ++jishu << ": "; 60 if(cnt!=n-1) {cout << "No" << endl;continue;} 61 sort(A+1,cmp2); 62 int high=kurscul(); 63 int rr=1; 64 while(brr[rr]<low) rr++; // 65 if(brr[rr]<=high) cout << "Yes" << endl; 66 else cout << "No" << endl; 67 } 68 return 0; 69 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |