HDOJ4786 Fibonacci Tree --- Kruskal算法+路徑壓縮并查集

題目連結 http://acm.hdu.edu.cn/showproblem.php?pid=4786

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 <= 105) and M(0 <= M <= 105).

　　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

題目大意：給t組測試資料。對于每組資料

輸入n個點，m條邊，然後m行對應每條邊，每行輸入每條邊連結的點編号以及 邊的顔色（1表示白色，0表示黑色）。

  問存不存在一個生成樹中白邊數量為Fibonacci數(即1,2,3,5,8...)

題解：可以看做每條邊權值都一樣，這樣用Kruskal算法每次篩最小邊時任意一條都算最小邊。

可以先根據顔色排序，第一次優先選擇黑色的邊（貪心思想），第二次優先選擇白色的邊。

如果不能形成生成樹，那直接no.

可以的話，可以算出形成生成樹時，白色邊數目的最小值min和最大值max,隻要[min,max]之間存在Fibonacci數就可以滿足題目條件（這個地方其實我暫時還沒有完全想懂...）。大概比如說算出來最小6條，最大10條白邊可以生成樹，

那說明在10條白邊那種情況下，删掉某4條白邊，補上某4條黑邊，可以轉換為前一種情形，是以一定可以删某2條白邊，補上2條黑邊達到8條白邊的生成樹滿足Fibonacci數的條件。

這道題要注意的是，用并查集找父親節點也就是Find函數，要用路徑壓縮處理，不然會導緻路徑太長逾時。（我剛開始就是沒路徑壓縮，然後逾時，不停比對别人的代碼，改來改去才發現是這個原因造成的逾時...）

 AC代碼：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 100005
using namespace std;
int pre[MAXN];// 并查集中的父親節點
int n,m;// 點數和邊數
bool fibonacci[MAXN];// 标記Fibonacci數
struct Edge {
  int u,v; // 連接配接的點編号
  int isWhite; // 是否是白色邊 
}edge[MAXN];
// 找并查集中的祖先節點
int Find(int x) {
   if(x != pre[x]) pre[x] = Find(pre[x]);
    return pre[x];
}
bool cmp1(Edge a,Edge b) {      
      return a.isWhite < b.isWhite;
}
bool cmp2(Edge a,Edge b) {      
     return b.isWhite < a.isWhite;
}

void Init() {	 
       for(int i = 1;i <= n;i++) 
           pre[i] = i;
}

/**
 * 克魯斯科爾算法求最小生成樹
 * @return int 傳回最少(多)的白邊數，-1表示無法生成樹
 */
int Kruskal() {
    Init();
    int ret = 0;// 傳回值
    int edgeNum = 0;// 選取的邊數    
    for(int i = 1;i <= m;i++) {
        int u = edge[i].u;
        int v = edge[i].v;
        int fu = Find(u);// u的祖先節點
        int fv = Find(v);// v的祖先節點
        if(fu == fv) {
            // 連接配接uv會形成閉環
            continue;
        }
        pre[fu] = fv;
        edgeNum++;
        if(edge[i].isWhite == 1)
            ret++;
        if(edgeNum == n - 1) {
            // 已經找到最小生成樹
            break;
        }
    }
    if(edgeNum != n-1)
        return -1;
    return ret;    
}

void CalFibonacci() {
    memset(fibonacci,0,sizeof(fibonacci));
    fibonacci[1] = fibonacci[2] = fibonacci[3] = true;
    int cur = 3,last = 2;
    while(cur+last < MAXN) {
        fibonacci[cur+last] = true;
        int temp = last + cur;
        last = cur;
        cur = temp;
    }
}
int main()
{
   int t;
   int Case = 1;
   scanf("%d",&t);
   CalFibonacci();
   while(t--) {       
       scanf("%d%d",&n,&m);
       for(int i = 1;i <= m;i++) {    
           scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].isWhite);           
       }
       sort(edge+1,edge+1+m,cmp1);// 對邊進行排序，邊的編号從1開始
       int minNum = Kruskal();// 最小白邊數
       sort(edge+1,edge+1+m,cmp2);// 對邊進行排序，邊的編号從1開始
       int maxNum = Kruskal(); 
	   if(minNum > maxNum)  swap(minNum,maxNum);
       if(minNum == -1) {
           printf("Case #%d: No\n",Case++);
           continue;
       }
       bool result = false;//标記是否滿足題目要求
       for(int i = minNum;i <= maxNum;i++) {
           if(fibonacci[i]) {
               result = true;
               break;
           }
       }
       if(result)
           printf("Case #%d: Yes\n",Case++);
       else
           printf("Case #%d: No\n",Case++);
   }   
   return 0; 
}