设为首页 - 加入收藏 焦点技术网
热搜:java
当前位置:首页 >

HDU 4786 Fibonacci Tree(生成树,YY乱搞)

2014-10-06 20:34:00.0 图论 YY乱搞 生成树 ACM algorithm 图论  
导读:http://acm.hdu.edu.cn/showproblem.php?pid=4786Fibonacci TreeTime Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1733    Accepted Submission(s): 543P...。。。

http://acm.hdu.edu.cn/showproblem.php?pid=4786

Fibonacci TreeTime Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1733    Accepted Submission(s): 543


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
24 41 2 12 3 13 4 11 4 05 61 2 11 3 11 4 11 5 13 5 14 2 1
 

Sample Output
Case #1: YesCase #2: No
 

Source
 

题意:
给出一个无向图,每条边都已染色(黑/白),问是否存在生成树,该生成树的白色边的数量是正的fibonacci数。
分析:
所给数据中黑边为0,白边为1,那么生成树的白边数量即为生成树的权和。
然后YY了一个做法:求其最小和最大生成树,如果在这个范围内存在fibonacci数则存在。
靠谱的证明方法一直没想出来,这里随便解释下:
对于任意一颗非最大生成树,一定可以取一条白边换一条黑边使其仍然是一颗树。


/* * * Author : fcbruce * * Time : Mon 06 Oct 2014 01:06:30 PM CST * */#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define sqr(x) ((x)*(x))#define LL long long#define itn int#define INF 0x3f3f3f3f#define PI 3.1415926535897932384626#define eps 1e-10#ifdef _WIN32  #define lld "%I64d"#else  #define lld "%lld"#endif#define maxm 100007#define maxn 100007using namespace std;int fib[maxn];struct _edge{  int u,v,w;  bool operator < (const _edge &_)const  {    return w<_.w;  }}edge[maxm];int pre[maxn];int root(int x){  if (x==pre[x]) return x;  return pre[x]=root(pre[x]);}bool same(int x,int y){  return root(x)==root(y);}void _merge(itn x,int y){  pre[root(x)]=root(y);}int cnt,fib_cnt;int main(){#ifdef FCBRUCE  freopen("/home/fcbruce/code/t","r",stdin);#endif // FCBRUCE    int T_T,__=0;  scanf("%d\n",&T_T);  fib[0]=1;  fib[1]=1;  fib_cnt=2;  for (int i=2;;i++)  {    fib[i]=fib[i-1]+fib[i-2];    fib_cnt++;    if (fib[i]>100000) break;  }  while (T_T--)  {    printf("Case #%d: ",++__);    int n,m;    scanf("%d%d",&n,&m);    for (int i=1;i<=n;i++) pre[i]=i;    cnt=n;    for (int i=0,u,v,w;i=0;i--)    {      u=edge[i].u;v=edge[i].v;w=edge[i].w;      if (!same(u,v))      {        _merge(u,v);        MAX+=w;        cnt--;        if (cnt==1) break;      }    }    int idmin=lower_bound(fib,fib+fib_cnt,MIN)-fib;    int idmax=lower_bound(fib,fib+fib_cnt,MAX)-fib;    if (fib[idmin]!=MIN && fib[idmax]!=MAX && idmin==idmax)      puts("No");    else      puts("Yes");      }  return 0;}


(编辑: u012965890)

网友评论
相关文章