Dfs

http://codeforces.com/contest/510/problem/B 题意：给定一个maze,用不同的字母代表不同的颜色。问能否找到一个颜色相同的环（失少四个点组成） 思路：dfs一遍，如果遇到之前已经访问过的点，说明成环。需要注意的是，要注意由一个点向某方向移动，然后由反方向移动到该点所造成的误判。所以dfs除了要知道当前的坐标x,y，还要记录之前的坐标px,py.

http://codeforces.com/contest/277/problem/A 题意：有n个人，每个人会一定数目的语言（可能为0），一个人学一门语言的代价为1，人和人之间沟通可以通过任意个中间人翻译。问最少的代价使得这n个人可以相互沟通。

http://codeforces.com/problemset/problem/217/A 题意：有n个雪漂（那是啥？，从某个雪漂出发走直线，只有到达另一个雪飘才能停下来。问最少需要添加多少个雪漂，才能使得可以到达任何一个雪漂。 思路：横坐标相同或者纵坐标相同的两个点之间是可以到达的。先O(N2)扫一遍建图。记录这个森林中数的个数为cnt,cnt-1即为答案。因为对于任意两个不能相互到达的点。我们只需要再来一个雪漂就可以使得这两个点相互到达。

http://codeforces.com/contest/445/problem/B 题意：一共有n种化学药品。m对关系，每对关系表示为x,y表示x和y相互反应。初始容器的danger值为1，当向容器中加入一个化学药品A,如果容器中存在化学药品和A反应，那么容器的danger值翻倍。否则不变。问一个最优的放置药品的顺序。

http://codeforces.com/problemset/problem/522/A 题意：给定某条消息的传播路径。问最远传播的距离。。 思路：其实就是问树的深度。。直接dfs就行了。。

http://codeforces.com/contest/377/problem/A 题意：给定一个n*m的maze. ‘.’代表空，‘#’代表墙。要求构造一种方案，使得将k个空格填成墙壁后不影响当前的连通性（即没有被填充的空格之间可以相互到达） 思路：一开始想从上往下从左往右构造。错误的认为四个角一定是可以变成墙的。

http://codeforces.com/contest/580/problem/C 题意：给出一棵树。每个叶子节点上有一个饭店。某些节点上有cat.现在问从根节点出发可以到达多少个饭店，保证在到达饭店的路径中补连续遇到m个以上的cat.

http://codeforces.com/problemset/problem/115/A 题意：给出n个人之间的上级下级关系。问如何分得最少的组，使得没一组中的人不存在上下级关系。 思路：用树的观点来考虑会很容易。可以看成给了一棵森冷。对于不同的树的相同层的点，不存在上下级关系，可以放在一个group.对于同一棵树，每一层要单独放一个group.所以答案是所有树的深度的最大值。

http://codeforces.com/contest/598/problem/D 题意：给第一个地图。 ‘.’是能走的，‘’是不能走的。**每个‘.’和’‘之间有一幅画，**给出k个起点，问对于每组起点，最多能观察到多少副画。

＿＿＿＿＿＿ 好蠢，竟然没看出来这道题的不同之处，以为就是个搜 然后样例什么的都过了．．．

dfs 1A 1/************************************************************************* 2 > File Name: code/whust/#9/K.cpp 3 > Author: 111qqz 4 > Email: rkz2013@126.com 5 > Created Time: 2015年08月05日 星期三 15时02分30秒 6 ************************************************************************/ 7 8#include<iostream> 9#include<iomanip> 10#include<cstdio> 11#include<algorithm> 12#include<cmath> 13#include<cstring> 14#include<string> 15#include<map> 16#include<set> 17#include<queue> 18#include<vector> 19#include<stack> 20#define y0 abc111qqz 21#define y1 hust111qqz 22#define yn hez111qqz 23#define j1 cute111qqz 24#define tm crazy111qqz 25#define lr dying111qqz 26using namespace std; 27#define REP(i, n) for (int i=0;i<int(n);++i) 28typedef long long LL; 29typedef unsigned long long ULL; 30const int inf = 0x7fffffff; 31int n ,m,ans; 32int d[50]; 33int on[50],off[50]; 34int u[50],v[50]; 35 36bool ok(int x,int y) 37{ 38 if ( !d[x] && !d[y] && on[x] == off[x] && on[y] == off[y] ) 39 return true; 40 if ( !d[x] && d[y] && on[x] == off[x] ) 41 return true; 42 if ( d[x] && !d[y] && on[y] == off[y] ) 43 return true; 44 if ( d[x] && d[y] ) 45 return true; 46 return false; 47} 48 49void dfs ( int i) 50{ 51 if (i==m) 52 { 53 ans++; 54 return; 55 } 56 int x = u[i]; 57 int y = v[i]; 58 d[x]--; 59 d[y]--; 60 on[x]++; 61 on[y]++; 62 if (ok(x,y)) 63 dfs (i+1); 64 on[x]--;on[y]--; 65 off[y]++;off[x]++; 66 if ( ok( x,y)) 67 dfs (i+1); 68 off[y]--; 69 off[x]--; 70 d[x]++; 71 d[y]++; 72} 73 74int main ( ) 75{ 76 int T; 77 cin>>T; 78 while ( T-- ) 79 { 80 ans = 0; 81 scanf ("%d %d",&n,&m); 82 memset (d,0,sizeof(d)); 83 memset (on,0,sizeof(on)); 84 memset (off,0,sizeof(off)); 85 for ( int i = 0 ; i < m ; i++ ) 86 { 87 scanf ("%d%d",&u[i],&v[i]); 88 d[u[i]]++; 89 d[v[i]]++; 90 } 91 dfs (0); 92 printf ( "%d\n" , ans ); 93 } 94}

“… so forward this to ten other people, to prove that you believe the emperor has 题意是说发短信,每个人只会给一个人发,问从哪个人开始发,能传到的人最多

Oil Deposits # **Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 17683 Accepted Submission(s): 10172 **

http://poj.org/problem?id=1564 dfs 三个参数 x,sum,k, x表示开始的坐标,sum表示当前的和,k表示这是一组答案中的第几个数,是用来记录路径的…