[HDOJ4786]Fibonacci Tree 最小生成树

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4786

先跑一遍最小生成树，注意判断是否已全部联通（用一个记号来统计最后生成树中有多少条边）。再记下最小生成树的权值和A。

再反向排序，求一遍最大生成树。记下权值和B。问题转换成求[A,B]内是否有斐波那契数存在。

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <iomanip>
  4 #include <cstring>
  5 #include <climits>
  6 #include <complex>
  7 #include <fstream>
  8 #include <cassert>
  9 #include <cstdio>
 10 #include <bitset>
 11 #include <vector>
 12 #include <deque>
 13 #include <queue>
 14 #include <stack>
 15 #include <ctime>
 16 #include <set>
 17 #include <map>
 18 #include <cmath>
 19 
 20 using namespace std;
 21 
 22 typedef struct P {
 23     int u;
 24     int v;
 25     int w;
 26 }P;
 27 
 28 bool cmp1(P p1, P p2) {return p1.w < p2.w;}
 29 bool cmp2(P p1, P p2) {return p1.w > p2.w;}
 30 int A, B;
 31 
 32 const int maxn = 100010;
 33 int n, m, cnt;
 34 int pre[maxn];
 35 int fib[maxn];
 36 P e[maxn];
 37 
 38 int find(int x) {
 39     return x == pre[x] ? pre[x] : pre[x] = find(pre[x]);
 40 }
 41 
 42 bool unite(int x, int y) {
 43     x = find(x);
 44     y = find(y);
 45     if(x != y) {
 46         pre[x] = y;
 47         return 1;
 48     }
 49     return 0;
 50 }
 51 
 52 void init() {
 53     for(int i = 0; i < maxn; i++) {
 54         pre[i] = i;
 55     }
 56 }
 57 
 58 void clear() {
 59     init();
 60     memset(e, 0, sizeof(e));
 61     A = 0, B = 0;
 62     cnt = 0;
 63 }
 64 
 65 int main() {
 66     // freopen("in", "r", stdin);
 67     int T;
 68     fib[0] = 0, fib[1] = 1, fib[2] = 1;
 69     for(int i = 3; i <= 26; i++) {
 70         fib[i] = fib[i-1] + fib[i-2];
 71     }
 72     scanf("%d", &T);
 73     for(int _ = 1; _ <= T; _++) {
 74         printf("Case #%d: ", _);
 75         clear();
 76         scanf("%d %d", &n, &m);
 77         for(int i = 0; i < m; i++) {
 78             scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w);
 79         }
 80         sort(e, e+m, cmp1);
 81         for(int i = 0; i < m; i++) {
 82             if(unite(e[i].u, e[i].v)) {
 83                 A += e[i].w;
 84                 cnt++;
 85             }
 86         }
 87         if(cnt != n - 1) printf("No
");
 88         else {
 89             init();
 90             sort(e, e+m, cmp2);
 91             for(int i = 0; i < m; i++) {
 92                 if(unite(e[i].u, e[i].v)) {
 93                     B += e[i].w;
 94                     cnt++;
 95                 }
 96             }
 97             int flag = 0;
 98             for(int i = 1; i <= 25; i++) {
 99                 if(fib[i] <= B && fib[i] >= A) {
100                     flag = 1;
101                     break;
102                 }
103             }
104             if(flag) printf("Yes
");
105             else printf("No
");
106         }
107     }
108 }

还排序个毛啊，直接反着跑一遍QAQ，反正有序的，二分查找一下不好吗。。。肥不拉几序列只要前25个，打一个小表就行了QAQ。。

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <iomanip>
  4 #include <cstring>
  5 #include <climits>
  6 #include <complex>
  7 #include <fstream>
  8 #include <cassert>
  9 #include <cstdio>
 10 #include <bitset>
 11 #include <vector>
 12 #include <deque>
 13 #include <queue>
 14 #include <stack>
 15 #include <ctime>
 16 #include <set>
 17 #include <map>
 18 #include <cmath>
 19 
 20 using namespace std;
 21 
 22 typedef struct P {
 23     int u;
 24     int v;
 25     int w;
 26 }P;
 27 
 28 bool cmp1(P p1, P p2) {return p1.w < p2.w;}
 29 bool cmp2(P p1, P p2) {return p1.w > p2.w;}
 30 int A, B;
 31 
 32 const int maxn = 100010;
 33 int n, m, cnt;
 34 int pre[maxn];
 35 int fib[maxn];
 36 P e[maxn];
 37 
 38 int find(int x) {
 39     return x == pre[x] ? pre[x] : pre[x] = find(pre[x]);
 40 }
 41 
 42 bool unite(int x, int y) {
 43     x = find(x);
 44     y = find(y);
 45     if(x != y) {
 46         pre[x] = y;
 47         return 1;
 48     }
 49     return 0;
 50 }
 51 
 52 void init() {
 53     for(int i = 0; i < maxn; i++) {
 54         pre[i] = i;
 55     }
 56 }
 57 
 58 void clear() {
 59     init();
 60     memset(e, 0, sizeof(e));
 61     A = 0, B = 0;
 62     cnt = 0;
 63 }
 64 
 65 void __FIB__() {
 66     fib[0]=0,fib[1]=1,fib[2]=1,fib[3]=2,fib[4]=3,fib[5]=5,
 67     fib[6]=8,fib[7]=13,fib[8]=21,fib[9]=34,fib[10]=55,
 68     fib[11]=89,fib[12]=144,fib[13]=233,fib[14]=377,
 69     fib[15]=610,fib[16]=987,fib[17]=1597,fib[18]=2584,
 70     fib[19]=4181,fib[20]=6765,fib[21]=10946,fib[22]=17711,
 71     fib[23]=28657,fib[24]=46368,fib[25]=75025;
 72 }
 73 
 74 int main() {
 75     // freopen("in", "r", stdin);
 76     // freopen("out", "w", stdout);
 77     int T;
 78     __FIB__();
 79     scanf("%d", &T);
 80     for(int _ = 1; _ <= T; _++) {
 81         printf("Case #%d: ", _);
 82         clear();
 83         scanf("%d %d", &n, &m);
 84         for(int i = 0; i < m; i++) {
 85             scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w);
 86         }
 87         sort(e, e+m, cmp1);
 88         for(int i = 0; i < m; i++) {
 89             if(unite(e[i].u, e[i].v)) {
 90                 A += e[i].w;
 91                 cnt++;
 92             }
 93         }
 94         if(cnt != n - 1) printf("No
");
 95         else {
 96             init();
 97             for(int i = m; i >= 0; i--) {
 98                 if(unite(e[i].u, e[i].v)) {
 99                     B += e[i].w;
100                     cnt++;
101                 }
102             }
103             int flag = 0;
104             int ll = 1, rr = 25;
105             while(ll < rr) {
106                 int mm = (ll + rr) >> 1;
107                 if(fib[mm] <= B && fib[mm] >= A) {
108                     flag = 1;
109                     break;
110                 }
111                 else if(fib[mm] > B) rr = mm;
112                 else if(fib[mm] < A) ll = mm + 1;
113             }
114             if(flag) printf("Yes
");
115             else printf("No
");
116         }
117     }
118 }