浙江财经大学
信工学院ACM集训队

HDU 4786 Fibonacci Tree(Kruskal)

本文由 Ocrosoft 于 2016-08-10 16:17:54 发表

Fibonacci Tree

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4187    Accepted Submission(s): 1304

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
 

Solution

题意:给出n个顶点,m条边,这些边有颜色,黑或白。问能不能构成一棵树,这棵树的白色边是斐波那契数。

思路:用Kruskal先判断能不能构成树,不能就No;Kruskal只用白色边构树,得到白色边最大值;只用黑色边构树,得到白色边最小值。如果这两个数之间有斐波那契数,就Yes。

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ms(a) memset(a,0,sizeof(a))
#define INF INT_MAX
#define MAXN 100000+10
using namespace std;
int n,m;
int pre[MAXN];
struct Edge
{
    int u,v,s;
} edge[MAXN];
int find(int x)
{
    if(pre[x]!=x)pre[x]=find(pre[x]);
    return pre[x];
}
int Kruskal(int s)
{
    int sum=0;
    for(int i=0; i<=n; i++)pre[i]=i;
    for(int i=1; i<=m; i++)
    {
        if(edge[i].s!=s)
        {
            int x=find(edge[i].u);
            int y=find(edge[i].v);
            if(x!=y)
            {
                pre[x]=y;
                sum++;
            }
        }
    }
    return sum;
}
int Fiboacii[MAXN]= {1,2};
int main()
{
    for(int i=2;; i++)
    {
        Fiboacii[i]=Fiboacii[i-1]+Fiboacii[i-2];
        if(Fiboacii[i]>MAXN)break;
    }
    int T,kase=0;
    cin>>T;
    while(T--)
    {
        printf("Case #%d: ",++kase);
        cin>>n>>m;
        for(int i=1; i<=m; i++)
            scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].s);
        if(Kruskal(2)!=n-1)printf("No\n");
        else
        {
            int maxn=Kruskal(0);
            int minn=n-Kruskal(1)-1;
            bool flag=0;
            for(int i=0; Fiboacii[i]<=maxn&&!flag; i++)
                if(Fiboacii[i]>=minn&&Fiboacii[i]<=maxn)flag=1;
            if(flag)printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}

 

欢迎转载,请保留出处与链接。Ocrosoft » HDU 4786 Fibonacci Tree(Kruskal)

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址