bnuoj 44359 快来买肉松饼

http://www.bnuoj.com/contest/problem_show.php?pid=44359

快来买肉松饼

Time Limit: 5000 ms Case Time Limit: 5000 ms Memory Limit: 32768 KB

Description

转眼又到了一年一度的圣战（光棍）节了，单身狗大表哥决定和一群一样孤独的盆友一起出来过节，一起玩游戏，输的人给赢的人买肉松饼，这样大家都不会感到孤单。

为了防止平局出现，大表哥给大家准备了一个奇数（大于一的奇数）个人可以围成一圈一起玩的游戏（每个人必须与两个人相邻）。大表哥希望大家都能参加到游戏里去，但无奈有些盆友之间有误会，有误会的盆友不能坐在相邻的位置一起愉快的玩耍。每个人可以同时参与多个游戏，但当所有能参与游戏的人数小于K时，大表哥将取消这次聚会。

Input

输入第一行一个整数T（T ≤ 100）表示共T组数据。

每组数据第一行三个数N，M，K表示大表哥共有N个盆友，M表示有M对误会关系，当所有参与人数大于等于K时大表哥举办聚会。（1 ≤ N≤ 1000 , 1 ≤ M ≤ 1000000,3 ≤ K)

接下来M行每行两个数a，b分别代表编号a和编号b的盆友间存在误会。（编号从1到n，误会关系可能重复）

Output

若大表哥可以举行聚会输出“Let's Fire!”，否则输出“What a Pity.”。

Sample Input

Sample Output

Let's Fire!

Source

FOJ有奖月赛-2014年11月

分析：

题目只要求和左右两个人没有冲突就满足题意，直接深搜到k个人即可 ， 否则就What a pity.

AC代码：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int N = 1e3 + ;

 int n, m, k, flag, vis[N], relation[N][N];

 void dfs(int s, int cur, int* res)

 {

     if(flag)

         return;

     if(cur >= k && relation[res[]][res[cur - ]])

     {

         flag = ;

         return;

     }

     for(int i = ; i <= n; i++)

     {

         if(relation[s][i] && !vis[i])

         {

             vis[i] = ;

             res[cur] = i;

             dfs(i, cur + , res);

             vis[i] = ;

         }

     }

 }

 int main()

 {

     int t;

     scanf("%d", &t);

     while(t--)

     {

         memset(relation, , sizeof(relation));

         memset(vis, , sizeof(vis));

         flag = ;

         scanf("%d%d%d", &n, &m, &k);

         while(m--)

         {

             int x, y;

             scanf("%d%d", &x, &y);

             relation[x][y] = ;

             relation[y][x] = ;

         }

         if(k > n)

         {

             printf("What a Pity.\n");

             continue;

         }

         int res[N];

         for(int i = ; i < n; i++)

             if(!flag)

                 dfs(i, , res);

         printf(flag ==  ? "Let's Fire!\n" : "What a Pity.\n");

     }

     return ;

 }

没有下面的代码会报TLE

         if(k > n)

         {

             printf("What a Pity.\n");

             continue;

         }

巴特西