首页 > 代码库 > FOJ 2181 快来买肉松饼

FOJ 2181 快来买肉松饼

链接:http://acm.fzu.edu.cn/problem.php?pid=2181

思路:乍一看以为是并查集,仔细想了下又找不到让函数结束的条件,所以就看了其他人的搜索大法

 1 #include <iostream> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <string.h> 5 #include <math.h> 6 #include <queue> 7 #include <algorithm> 8 typedef long long ll; 9 using namespace std;10 11 int map[10005][10005],vis[10005],p[10005],flag;12 int cas,n,m,k,a,b;13 14 void dfs(int s,int cur,int *p)15 {16     if(flag)17         return;18     if(cur>=k && map[p[cur]][p[cur-1]])19     {20         flag=1;21         return;22     }23     for(int i=1;i<=n;i++)24     {25         if(map[s][i] && !vis[i])26         {27             vis[i]=1;28             p[cur]=i;29             dfs(i,cur+1,p);30             vis[i]=0;31         }32     }33 }34 35 36 int main()37 {38     39     scanf("%d",&cas);40     while(cas--)41     {42         memset(vis,0,sizeof(vis));43         memset(map,1,sizeof(map));44         scanf("%d %d %d",&n,&m,&k);45         for(int i=0;i<m;i++)46         {47             scanf("%d %d",&a,&b);48             map[a][b]=map[b][a]=0;49         }50         if(k>n)51         {52             printf("What a Pity.\n");53             continue;54         }55         56         for(int i=1;i<n;i++)57             if(!flag)58                 dfs(i,0,p);59         if(flag)60             printf("Let‘s Fire!\n");61         else62             printf("What a Pity.\n");63     }64     return 0;65  } 

 

FOJ 2181 快来买肉松饼