BFS和DFS算是比较基本的东西了，最近一直在做Lightoj这部分的专题，目前进度是10/27。

###LightOJ 1009

求对立的两方中最大的人数，做一遍DFS即可。

###LightOJ 1012

求王子的最大活动范围，依然是一遍DFS，然后记录。

###LightOJ 1039

这个木有用DFS做，建图后用SPFA做的。

LightOJ 1039
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
//By Brickgao
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;

const int Maxn = 18000;
const int Maxm = 220000;

typedef struct Edge{
    int to, nxt;
}Edge;

Edge rec[Maxm];
int head[Maxn], dist[Maxn], que[Maxm];
bool visit[Maxn], forbid[Maxn];
int cnt = 0, caseno = 1, start, end;
string a, b;

void add(int u, int v)
{
    rec[cnt].nxt = head[u];
    rec[cnt].to = v;
    head[u] = cnt ++;
    rec[cnt].nxt = head[v];
    rec[cnt].to = u;
    head[v] = cnt ++;
}

int get_num(string s)
{
    int ans = s[0] - 'a' + (s[1] - 'a') * 26 + (s[2] - 'a') * 26 * 26;
    return ans;
}

void reset_graph()
{
    for(int i = 0; i < 26; i ++)
        for(int j = 0; j < 26; j ++)
            for(int k = 0; k < 26; k ++)
            {
                int num1, num2;
                string tmp1 = "";
                tmp1 += 'a' + i; tmp1 += 'a' + j; tmp1 += 'a' + k;
                num1 = get_num(tmp1);
                for(int p = 0; p < 3; p ++)
                {
                    string tmp2 = tmp1;
                    tmp2[p] --;
                    if(tmp2[p] < 'a')   tmp2[p] = 'z';
                    num2 = get_num(tmp2);
                    add(num1, num2);
                    tmp2 = tmp1;
                    tmp2[p] ++;
                    if(tmp2[p] > 'z')   tmp2[p] = 'a';
                    num2 = get_num(tmp1);
                    add(num1, num2);
                }
            }
}

void spfa()
{
    int h = 0 , f = 0 ;
    que[++ f] = start ; dist[start] = 0 ;
    visit[start] = true;
    while (h <= f)
    {
        int u = que[++ h];
        for(int i = head[u]; i != -1; i = rec[i].nxt)
        {
            int v = rec[i].to;
            if (forbid[v]) continue;
            if (dist[u] + 1 < dist[v])
            {
                dist[v] = dist[u] + 1;
                if (!visit[v])
                {
                    que[++ f] = v;
                    visit[v] = true;
                }
            }
            visit[u] = false;
        }
    }
}

void solve()
{
    if(forbid[start] || forbid[end])
    {
        printf("Case %d: -1\n", caseno ++);
        return;
    }
    spfa();
    if(dist[end] != 32766)
        printf("Case %d: %d\n", caseno ++, dist[end]);
    else
        printf("Case %d: -1\n", caseno ++);
}

void init()
{
    char s1[26], s2[26], s3[26];
    int n;
    memset(dist, Maxn, sizeof(dist));
    memset(visit, false, sizeof(visit));
    memset(forbid, false, sizeof(forbid));
    cin >> a >> b;
    start = get_num(a);
    end = get_num(b);
    scanf("%d", &n);
    for(int i = 0; i < n; i ++)
    {
        scanf("%s %s %s", s1, s2, s3);
        for(int ii = 0; ii < strlen(s1); ii ++)
            for(int jj = 0; jj < strlen(s2); jj ++)
                for(int kk = 0; kk < strlen(s3); kk++)
                {
                    string tmp = "";
                    tmp += s1[ii]; tmp += s2[jj]; tmp += s3[kk];
                    forbid[get_num(tmp)] = true;
                }
    }
}

int main()
{
    int t;
    memset(head, -1, sizeof(head));
    reset_graph();
    scanf("%d", &t);
    while(t --)
    {
        init();
        solve();
    }
    return 0;
}

###LightOJ 1046

求把骑士聚合到一点所花费的最少时间，对每一个骑士做一遍DFS即可。

###LightOJ 1049

因为一个点只有两条有向边，所以肯定是成环的。

###LightOJ 1055

每次移动三个点，终于明白BFS比DFS在求最小值的时候优越的多= =。

###LightOJ 1066

按顺序收集，就对相邻字母DFS。

###LightOJ 1094

从Forum学习了一下如何一颗树上最远的两个点，每次求以该点为根的最大点和次大点处理。

LightOJ 1094
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//By Brickgao
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;

#define pb push_back
#define cl clear

typedef struct record{
	int to, w;
}record;

int t, caseno = 1, n, ans, dist[30010][2];
bool visit[30010];
vector <record> p[30010];

void dfs(int u)
{
	bool done = false;
	int max1 = 0, max2 = 0;
	for(int i = 0; i < p[u].size(); i ++)
	{
		int v = p[u][i].to;
		if(!visit[v])
		{
			done = true;
			visit[v] = true;
			dfs(v);
			int total = max(dist[v][0], dist[v][1]);
			//cout << u << "->" << v << " " << dist[v] + p[u][i].w << endl;
			if(total + p[u][i].w > max2 && total + p[u][i].w <= max1)
				max2 = total + p[u][i].w;
			if(total + p[u][i].w > max1)
			{
				max2 = max1;
				max1 = total + p[u][i].w;
				//cout << "change: " << max1 << endl;
			}
		}
	}
	//cout << max1 << "***" << max2 << endl;
	if(done)
	{
		if(max2 == 0)
			dist[u][0] = max1;
		else
		{
			dist[u][0] = max1;
			dist[u][1] = max2;
		}
	}
}

void init()
{
	int u, v, w;
	record tmp;
	ans = 0;
	scanf("%d", &n);
	for(int i = 0; i < n; i ++)
		p[i].cl();
	for(int i = 0; i < n - 1; i ++)
	{
		scanf("%d%d%d", &u, &v, &w);
		tmp.w = w;
		tmp.to = v; p[u].pb(tmp);
		tmp.to = u; p[v].pb(tmp);
	}
}

void solve()
{
	for(int i = 0; i <= n; i ++)
	{
		visit[i] = false;
		dist[i][0] = dist[i][1] = 0;
	}
	visit[0] = true;
	dfs(0);
	for(int i = 0; i < n; i ++)
	{
		//cout << dist[i] << endl;
		ans = max(ans, dist[i][0] + dist[i][1]);
	}
	printf("Case %d: %d\n", caseno ++, ans);
}

int main()
{
	scanf("%d", &t);
	while(t --)
	{
		init();
		solve();
	}
    return 0;
}

###Lightoj 1111

求所有人聚餐地点，对做一遍所有人DFS。

###Lightoj 1141

先求出1 - 1000 的素因子，然后DFS就行了