首页 > 代码库 > 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 快来买肉松饼
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。