问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3259思路:
这题的描述挺有意思，通过某些路径可以回到过去之类，其实就是求是否存在负权回路的问题
Bellman-Ford算法的典型应用
一个问题是，Bellman-Ford用于判断从某个源点可达的负权回路，而这里求的是整个图，而且也没有说明该图一定是connected的
解决上述问题的一个方法就是添加一个顶点，然后从该新顶点到每个其他顶点添加一条权值为0的边
代码:
1 /* Bellman-Ford algorithm */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_N 501
6 #define MAX_M 2501
7 #define MAX_W 201
8 #define INF 0x7FFFFFFF
9 struct Edge {
10 int from, to;
11 int cost;
12 } edges[MAX_M*2+MAX_W+MAX_N];
13 int d[MAX_N];
14 int n, total;
15
16 void
17 init()
18 {
19 int i, m, w, f, t, c;
20 scanf("%d %d %d", &n, &m, &w);
21 total = 0; /* the number of edges */
22 for(i=0; i<m; i++) {
23 scanf("%d %d %d", &f, &t, &c);
24 edges[total].from = f;
25 edges[total].to = t;
26 edges[total++].cost = c;
27 edges[total].from = t;
28 edges[total].to = f;
29 edges[total++].cost = c;
30 }
31 for(i=0; i<w; i++) {
32 scanf("%d %d %d", &f, &t, &c);
33 edges[total].from = f;
34 edges[total].to = t;
35 edges[total++].cost = c*(-1);
36 }
37 /* in order to keep connectivity, add one vertex: '0' */
38 for(i=1; i<=n; i++) {
39 edges[total].from = 0;
40 edges[total].to = i;
41 edges[total++].cost = 0;
42 }
43 }
44
45 void
46 relax(struct Edge *e)
47 {
48 if(d[e->from] == INF)
49 return;
50 if(d[e->to] > d[e->from]+e->cost)
51 d[e->to] = d[e->from]+e->cost;
52 }
53
54 int
55 bellman_ford()
56 {
57 int i, j;
58 for(i=0; i<=n; i++)
59 d[i] = INF;
60 d[0] = 0;
61 for(i=0; i<n; i++) /* n+1 vertices */
62 for(j=0; j<total; j++) /* 2*m+w+n edges */
63 relax(edges+j);
64 for(j=0; j<total; j++) {
65 if(d[edges[j].to] > d[edges[j].from]+edges[j].cost)
66 return 0;
67 }
68 return 1;
69 }
70
71 int
72 main(int argc, char **argv)
73 {
74 int F;
75 scanf("%d", &F);
76 while(F--) {
77 init();
78 printf("%s\n", bellman_ford()==1?"NO":"YES");
79 }
80 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2394思路:
题目说的有点复杂，其实就是求单源最短路径，Dijkstra算法
需要注意的是输入可能有重边
具体关于Dijkstra算法，参考算法导论，有详细的证明
第一次写该算法，一次AC o(∩_∩)o...哈哈
代码:
1 /* dijkstra algorithm */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_F 501
6 #define MAX_C 101
7 #define INF 0x7FFFFFFF
8 int adj[MAX_F][MAX_F];
9 int pos[MAX_C];
10 int in[MAX_F], d[MAX_F];
11 int f, p, c, m;
12
13 void
14 init()
15 {
16 int i, from, to, cost;
17 memset(adj, 0, sizeof(adj));
18 scanf("%d %d %d %d", &f, &p, &c, &m);
19 for(i=0; i<p; i++) {
20 scanf("%d %d %d", &from, &to, &cost);
21 if(adj[from][to]==0 || adj[from][to]>cost)
22 adj[from][to] = adj[to][from] = cost;
23 }
24 for(i=1; i<=c; i++)
25 scanf("%d", pos+i);
26 }
27
28 void
29 dijkstra()
30 {
31 int i, j, k, cur;
32 memset(in, 0, sizeof(in));
33 for(i=1; i<=f; i++)
34 d[i] = INF;
35 d[1] = 0;
36 in[1] = 1;
37 for(j=1; j<=f; j++)
38 if(!in[j] && adj[1][j])
39 d[j] = adj[1][j];
40 for(i=2; i<=f; i++) {
41 cur = INF;
42 for(j=1; j<=f; j++)
43 if(!in[j] && d[j]<=cur) {
44 k = j;
45 cur = d[j];
46 }
47 in[k] = 1;
48 for(j=1; j<=f; j++)
49 if(!in[j] && adj[k][j] && d[k]!=INF)
50 if(d[j] > d[k]+adj[k][j])
51 d[j] = d[k]+adj[k][j];
52 }
53 }
54
55 void
56 output()
57 {
58 int i, n = 0;
59 for(i=1; i<=c; i++)
60 if(d[pos[i]] <= m) {
61 ++n;
62 pos[i] = -1;
63 }
64 printf("%d\n", n);
65 for(i=1; i<=c; i++)
66 if(pos[i] == -1)
67 printf("%d\n", i);
68 }
69
70 int
71 main(int argc, char **argv)
72 {
73 init();
74 dijkstra();
75 output();
76 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1054思路:
好题，枚举 + 二分
枚举所有可能路径的前两个点
要注意的是:
starting outside the paddy on one side and ending outside the paddy on the other side代码:
1 /* enumerate the first two points for each possible path */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_NUM 5001
6 #define is_valid(x, y) ((x)>0 && (x)<=R && (y)>0 && (y)<=C)
7 int R, C;
8 int total;
9 struct Point {
10 int x, y;
11 } points[MAX_NUM];
12
13 /* from top to down, and left to right */
14 int
15 compare(const void *arg1, const void *arg2)
16 {
17 struct Point *a = (struct Point *)arg1;
18 struct Point *b = (struct Point *)arg2;
19 if(a->x == b->x)
20 return a->y - b->y;
21 return a->x - b->x;
22 }
23
24 void
25 init()
26 {
27 int i;
28 scanf("%d", &total);
29 for(i=0; i<total; i++)
30 scanf("%d %d", &points[i].x, &points[i].y);
31 qsort(points, total, sizeof(struct Point), compare);
32 }
33
34 void
35 solve()
36 {
37 int i, j, tmp, max = 0;
38 int diff_x, diff_y;
39 struct Point p1, p2, next;
40 struct Point *ptr;
41 for(i=0; i<total; i++) {
42 for(j=i+1; j<total; j++) {
43 tmp = 2;
44 p1 = points[i];
45 p2 = points[j];
46 diff_x = p2.x - p1.x;
47 diff_y = p2.y - p1.y;
48 if(is_valid(p1.x-diff_x, p1.y-diff_y)) /* starting outside */
49 continue;
50 if(!is_valid(p1.x+max*diff_x, p1.y+max*diff_y)) /* pruning */
51 continue;
52 next.x = p2.x + diff_x;
53 next.y = p2.y + diff_y;
54 while(is_valid(next.x, next.y)) {
55 if((ptr=(struct Point *)bsearch(&next, points, total, sizeof(struct Point), compare)) == NULL) {
56 tmp = 0; /* ending outside */
57 break;
58 }
59 ++tmp;
60 next.x += diff_x;
61 next.y += diff_y;
62 }
63 max = tmp>max ? tmp : max;
64 }
65 }
66 printf("%d\n", max>2 ? max : 0);
67 }
68
69 int
70 main(int argc, char **argv)
71 {
72 while(scanf("%d %d", &R, &C) != EOF) {
73 init();
74 solve();
75 }
76 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2421思路:
非常类似于PKU 2485 Highways
区别在于: "
there are already some roads between some villages"
如何在求最小生成树的算法中体现某些路径已经存在了呢？
对于Prim算法，只要将已经存在的路径(u, v)的权重设置为0即可（为什么？）
对于Kruskal算法，比较容易理解，只要将已经存在的路径(u, v)进行Union操作即可，即将u, v看作是一个连通域
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1861http://acm.pku.edu.cn/JudgeOnline/problem?id=2485思路:
这里题目并没有明确要求求最小生成树，而是要求一颗最长边最小的生成树
我们可以证明:
如果T是一颗最小生成树，那么T所包含的最长边一定是所有生成树中最小的，即最小生成树满足题目要求
Prove:
如果T的最长边(x, y)并非最小
那么，存在一颗生成树R，其最长边(u, v)<(x, y)，即生成树R的任何一条边都小于(x, y)
现在，采用剪切-粘帖的方法来证明T不是一颗最小生成树，即矛盾
将T中的最长边(x, y)剪切掉，这样就得到两颗子树
在R中，至少存在一条边(p, q)可以将这两颗子树连接起来，这样就得到:
T - (x, y) + (p, q) < T
代码(这里采用Kruskal算法，并查集实现)
1 /* union-find sets, Kruskal algorithm */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_N 1001
6 #define MAX_M 15001
7 struct Edge{
8 int len;
9 int from, to;
10 }edges[MAX_M];
11 int parent[MAX_N], rank[MAX_N];
12 int n, m;
13
14 void
15 make_set()
16 {
17 int i;
18 for(i=1; i<=n; i++)
19 parent[i] = i;
20 memset(rank, 0, sizeof(rank));
21 }
22
23 int
24 find(int x)
25 {
26 int tmp, rt = x;
27 while(parent[rt] != rt)
28 rt = parent[rt];
29 while(x != rt) {
30 tmp = parent[x];
31 parent[x] = rt;
32 x = tmp;
33 }
34 return rt;
35 }
36
37 void
38 Union(int x, int y)
39 {
40 int a = find(x);
41 int b = find(y);
42 if(a == b)
43 return;
44 if(rank[a] > rank[b])
45 parent[b] = a;
46 else {
47 parent[a] = b;
48 if(rank[a] == rank[b])
49 ++rank[b];
50 }
51 }
52
53 int
54 compare(const void *arg1, const void *arg2)
55 {
56 return ((struct Edge *)arg1)->len - ((struct Edge *)arg2)->len;
57 }
58
59 void
60 init()
61 {
62 int i;
63 for(i=0; i<m; i++)
64 scanf("%d %d %d", &edges[i].from, &edges[i].to, &edges[i].len);
65 qsort(edges, m, sizeof(struct Edge), compare);
66 }
67
68 void
69 kruskal()
70 {
71 int i, a, b, count = 0;
72 int mark[MAX_N];
73 make_set();
74 for(i=0; i<m; i++) {
75 a = find(edges[i].from);
76 b = find(edges[i].to);
77 if(a != b) {
78 mark[count++] = i;
79 Union(a, b);
80 }
81 }
82 /* output */
83 printf("%d\n", edges[mark[count-1]].len);
84 printf("%d\n", count);
85 for(i=0; i<count; i++)
86 printf("%d %d\n", edges[mark[i]].from, edges[mark[i]].to);
87 }
88
89 int
90 main(int argc, char **argv)
91 {
92 while(scanf("%d %d", &n, &m) != EOF) {
93 init();
94 kruskal();
95 }
96 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1251http://acm.pku.edu.cn/JudgeOnline/problem?id=1258思路:
最简单典型的最小生成树，PRIM算法
参考算法导论
代码(pku 1251):
1 /* MST problem */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_LEN 27
6 #define INF 0x7FFFFFFF
7 int num, min;
8 int adj[MAX_LEN][MAX_LEN];
9 int key[MAX_LEN], in[MAX_LEN];
10
11 void
12 init()
13 {
14 int i, j, k, dis;
15 char tmp[2], tmp1[2];
16 memset(adj, 0, sizeof(adj));
17 memset(in, 0, sizeof(in));
18 min = 0;
19 for(i=0; i<num; i++)
20 key[i] = INF;
21 for(i=0; i<num-1; i++) {
22 scanf("%s %d", tmp, &k);
23 for(j=0; j<k; j++) {
24 scanf("%s %d", tmp1, &dis);
25 adj[tmp[0]-'A'][tmp1[0]-'A'] = dis;
26 adj[tmp1[0]-'A'][tmp[0]-'A'] = dis;
27 }
28 }
29 }
30
31 void
32 prim()
33 {
34 int i, j, k, cur;
35 /* start from vertex 'A' */
36 in[0] = 1;
37 for(i=1; i<num; i++)
38 if(adj[0][i])
39 key[i] = adj[0][i];
40 for(i=1; i<num; i++) { /* num-1 vertex left */
41 cur = INF;
42 for(j=0; j<num; j++) {
43 if(!in[j] && key[j]<cur) {
44 cur = key[j];
45 k = j;
46 }
47 }
48 min += cur;
49 in[k] = 1;
50 for(j=0; j<num; j++) {
51 if(adj[k][j]) {
52 if(!in[j] && adj[k][j]<key[j])
53 key[j] = adj[k][j];
54 }
55 }
56 }
57 }
58
59 int
60 main(int argc, char **argv)
61 {
62 while(scanf("%d", &num)!=EOF && num) {
63 init();
64 prim();
65 printf("%d\n", min);
66 }
67 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3687思路:
这题理解起来就很困难，等理解透了也还是不会
参考:
http://hi.baidu.com/archersfate/blog/item/30e66f76734a0c12b051b9ab.html总结:
逆向的拓扑排序，等同于对转置图进行正向的拓扑排序（其实就是入度与出度的区别）
DFS实现拓扑排序适合于求出所有可能的解
BFS实现拓扑排序适合于求出满足特定要求的解
代码:
1 /* cpp: priority_queue */
2 #include<iostream>
3 #include<queue>
4 #include<vector>
5 #include<functional>
6 #include<cstdio>
7 #include<cstring>
8 using namespace std;
9
10 #define MAX_N 201
11 int n, m;
12 int adj[MAX_N][MAX_N];
13 int out_degree[MAX_N], topo[MAX_N], ans[MAX_N];
14
15 void
16 init()
17 {
18 int i, pre, suc;
19 memset(adj, 0, sizeof(adj));
20 memset(out_degree, 0, sizeof(out_degree));
21 scanf("%d %d", &n, &m);
22 for(i=0; i<m; i++) {
23 scanf("%d %d", &pre, &suc);
24 if(!adj[pre][suc]) { /* avoid duplicates */
25 adj[pre][suc] = 1;
26 ++out_degree[pre];
27 }
28 }
29 }
30
31 void
32 reverse_topo_sort()
33 {
34 int i, tmp, count = 0;
35 priority_queue<int, vector<int>, less<int> > Q;
36 for(i=1; i<=n; i++)
37 if(out_degree[i] == 0)
38 Q.push(i);
39 while(!Q.empty()) { /* BFS */
40 tmp = Q.top();
41 Q.pop();
42 topo[++count] = tmp;
43 for(i=1; i<=n; i++)
44 if(adj[i][tmp]) {
45 --out_degree[i];
46 if(!out_degree[i])
47 Q.push(i);
48 }
49 }
50 if(count != n) { /* not DAG */
51 printf("-1\n");
52 return;
53 }
54 for(i=1; i<=n; i++)
55 ans[topo[n-i+1]] = i;
56 for(i=1; i<=n; i++)
57 printf("%d ", ans[i]);
58 printf("\n");
59 }
60
61 int
62 main(int argc, char **argv)
63 {
64 int tests;
65 scanf("%d", &tests);
66 while(tests--) {
67 init();
68 reverse_topo_sort();
69 }
70 }
转载:
PKU 3687 在基本的拓扑排序的基础上又增加了一个要求：编号最小的节点要尽量排在前面；在满足上一个条件的基础上，编号第二小的节点要尽量排在前面；在满足前两个条件的基础上，编号第三小的节点要尽量排在前面……依此类推。（注意，这和字典序是两回事，不可以混淆。）
如图 1 所示，满足要求的拓扑序应该是：6 4 1 3 9 2 5 7 8 0。
图 1 一个拓扑排序的例子
一般来说，在一个有向无环图中，用 BFS 进行拓扑排序是比较常见的做法
做法，如算法 1 所示。但是它不一定能得到本题要求的拓扑序。
1. 把所有入度为 0 的节点放进队列 Q
2. WHILE： Q 不是空队列
3. 从 Q 中取出队列首元素 a，把 a 添加到答案的尾部。
4. FOR：所有从 a 出发的边 a → b
5. 把 b 的入度减 1。如果 b 的入度变为 0，则把 b 放进队列 Q。 |
算法 1 用 BFS 进行拓扑排序
为了解决本问题，下面让我来探究一下拓扑序的一些性质。以图 1 为例，节点 0 毫无疑问排在最后。除了节点 0 以外，有三条互相平行的路径：6 → 4 → 1、 3→ 9 → 2 和 5 → 7 → 8。一条路径上的各个节点的先后关系都是不能改变的，比如路径 6 → 4 → 1 上的三个节点在拓扑序中，一定是 6 在最前，1 在最后。但是，互相平行的各条路径，在总的拓扑序中任意交错都是合法的。比如，以下都是图 1 的合法拓扑序：
6 4 1 3 9 2 5 7 8 0、 3 6 9 4 5 1 7 8 2 0、 5 6 4 7 3 8 1 9 2 0、 3 5 6 4 1 7 9 2 8 0、 6 5 7 8 4 3 9 2 1 0。
怎么才能找出题目要求的拓扑序呢？在这里，我想用字典序最先的拓扑序来引出这个算法。算法 2 可以求出字典序最先的拓扑序。
1. 把所有入度为 0 的节点放进优先队列 PQ
2. WHILE： PQ 不是空队列
3. 从 PQ 中取出编号最小的元素 a，把 a 添加到答案的尾部。
4. FOR：所有从 a 出发的边 a → b
5. 把 b 的入度减 1。如果 b 的入度变为 0，则把 b 放进优先队列 PQ。 |
算法 2 求出字典序最先的拓扑序
可见，算法 2 和算法 1 基本一样，只是把队列改成了优先队列。用它求出的图 1 的字典序最先的拓扑序为：3 5 6 4 1 7 8 9 2 0。但是这显然不是本题要求的答案，因为节点 1 的位置还不够靠前。
算法 2 可以算是一个贪心算法，每一步都找编号最小的节点。但是对于图 1 中的三条路径，头的编号比较小的，不一定要先出队列。正确的步骤应该如下：
- 节点 0 的位置是铁定在最后的，不用考虑。只考虑剩下的三条路径。
- 先找编号最小的，节点 1。把它和它所在的路径中位于它前面的节点全部拿出来。目前的答案是 6 4 1，这样， 节点 1 就尽量靠前了。
- 再找剩下的节点中编号最小的，节点 2。把它和它所在的路径中位于它前面的节点全部拿出来。目前的答案是 6 4 1 3 9 2 ，这样，节点 2 就尽量靠前了。
- 只剩下一条路径了，只能依次把其中的节点拿出来。最后答案就是 6 4 1 3 9 2 5 7 8 0。
显然，算法 2 的贪心策略对于这个问题是不可行的。不能着眼于每条路径的头，而是要找编号最小的节点在哪条路径上，优先把这条路径拿出来。但问题在于，在 BFS 的过程中，我们只能看到每条路径的头，看不到后面的节点，这该怎么办呢？
让我们换个角度想一想，节点 3 和 6，应该是 6 先出队列，因为节点 1 在 6 的后面。这和节点 3 和 6 的编号大小没有任何关系。但是，再看另外两条路径的尾部，节点 2 和 8，可以肯定地说，2 一定先出队列，因为它们后面都没有别的节点了，这个时候完全以这两个节点本身的编号大小决定顺序。归纳起来就是说，对于若干条平行的路径，小的头部不一定排在前面，但是大的尾部一定排在后面。于是，就有了算法 3。
1. 把所有出度为 0 的节点放进优先队列 PQ
2. WHILE： PQ 不是空队列
3. 从 PQ 中取出编号最大的元素 a，把 a 添加到答案的头部。
4. FOR：所有指向 a 的边 b → a
5. 把 b 的出度减 1。如果 b 的出度变为 0，则把 b 放进优先队列 PQ。 |
算法 3 求出本题目要求的拓扑序
我觉得这道题目确实挺奥妙的，我搞了很久才想通算法 3 为什么是正确的，特地在此写一下。
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1664思路:
就是根据题意进行DFS，要注意的是如何避免重复: 所放苹果数目递减
居然一会就AC了哈哈，暑假的锻炼还是有些成果的：）
代码:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 int n, m;
5 int total;
6
7 void
8 dfs(int level, int left, int last)
9 {
10 int i, up;
11 if(level==n) {
12 if(left == 0)
13 ++total;
14 return;
15 }
16 up = left<last ? left : last;
17 for(i=up; i>=0; i--)
18 dfs(level+1, left-i, i);
19 }
20
21 int
22 main(int argc, char **argv)
23 {
24 int tests;
25 scanf("%d", &tests);
26 while(tests--) {
27 scanf("%d %d", &m, &n);
28 total = 0;
29 dfs(0, m, m);
30 printf("%d\n", total);
31 }
32 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1128思路:
想法是有：先找出没有被任何其他frame覆盖的frame，然后将该frame进行标记，使之匹配任何字母，然后重复以上过程
不过，程序不知道该如何写
参考discuss以及其他人思路，发现可以用拓扑排序来做（拓扑排序，参考算法导论)
如何根据输入来建立邻接矩阵比较有意思，另外根据各个顶点的入度DFS实现拓扑排序
代码:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 31
5 #define MAX_NUM 27
6 char map[MAX_LEN][MAX_LEN];
7 int n, m;
8 int adj[MAX_NUM][MAX_NUM], num, in[MAX_NUM], visited[MAX_NUM];
9 int x1, y1, x2, y2;
10
11 void
12 search(char ch)
13 {
14 int i, j;
15 x1 = y1 = MAX_LEN;
16 x2 = y2 = -1;
17 for(i=0; i<n; i++)
18 for(j=0; j<m; j++)
19 if(map[i][j] == ch) {
20 if(i<x1) x1 = i;
21 if(i>x2) x2 = i;
22 if(j<y1) y1 = j;
23 if(j>y2) y2 = j;
24 }
25 }
26
27 void
28 build_graph()
29 {
30 int i, j, k;
31 char ch;
32 num = 0;
33 memset(adj, 0, sizeof(adj));
34 memset(in, -1, sizeof(in));
35 for(i=0; i<n; i++) {
36 for(j=0; j<m; j++) {
37 if(map[i][j]=='.' || in[map[i][j]-'A']>-1)
38 continue;
39 in[map[i][j]-'A'] = 0;
40 ++num;
41 search(map[i][j]);
42 for(k=x1; k<=x2; k++) {
43 ch = map[k][y1];
44 if(ch != map[i][j])
45 adj[map[i][j]-'A'][ch-'A'] = 1;
46 }
47 for(k=x1; k<=x2; k++) {
48 ch = map[k][y2];
49 if(ch != map[i][j])
50 adj[map[i][j]-'A'][ch-'A'] = 1;
51 }
52 for(k=y1; k<=y2; k++) {
53 ch = map[x1][k];
54 if(ch != map[i][j])
55 adj[map[i][j]-'A'][ch-'A'] = 1;
56 }
57 for(k=y1; k<=y2; k++) {
58 ch = map[x2][k];
59 if(ch != map[i][j])
60 adj[map[i][j]-'A'][ch-'A'] = 1;
61 }
62 }
63 }
64 for(i=0; i<MAX_NUM; i++)
65 for(j=0; j<MAX_NUM; j++)
66 if(adj[i][j])
67 ++in[j]; /* in-degree */
68 }
69
70 void
71 topological_sort(char *str, int level)
72 {
73 int i, j;
74 if(level == num) {
75 printf("%s\n", str);
76 return;
77 }
78 for(i=0; i<MAX_NUM; i++) {
79 if(in[i]==0 && !visited[i]) {
80 str[level] = 'A'+i;
81 visited[i] = 1;
82 for(j=0; j<MAX_NUM; j++)
83 if(adj[i][j])
84 --in[j];
85 topological_sort(str, level+1);
86 visited[i] = 0;
87 for(j=0; j<MAX_NUM; j++)
88 if(adj[i][j])
89 ++in[j];
90 }
91 }
92 }
93
94 int
95 main(int argc, char **argv)
96 {
97 int i;
98 char str[MAX_NUM];
99 while(scanf("%d %d", &n, &m)!=EOF) {
100 for(i=0; i<n; i++)
101 scanf("%s", map[i]);
102 build_graph();
103 memset(str, 0, sizeof(str));
104 memset(visited, 0, sizeof(visited));
105 topological_sort(str, 0);
106 }
107 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1324参考:
http://hi.baidu.com/aekdycoin/blog/item/08774afbd1a29316a8d31111.htmlhttp://clover520.blogbus.com/logs/38001465.html思路:
用BFS求最短路径肯定是没有问题的，关键是状态如何表示
参考别人的思路，原来蛇身只需要通过上、下、左、右四个方向表示即可(两bits或4进制)，这样可以很大程度上减少空间，而且判重也就不再是个问题，只需要用三维数组表示即可
不过我自己写出来的代码却总是MLE，悲剧...(无奈，贴了别人代码过的，无耻啊)
代码:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4
5 int kk[4][2]={1,0,0,1,0,-1,-1,0},N,M,L;
6 struct point{
7 char x,y;
8 int dis,body;
9 };
10 int bfs();
11 int main(){
12 int Cas=0;
13 while(scanf("%d%d%d",&N,&M,&L)==3){
14 if(N==0&&M==0&&L==0)break;
15 printf("Case %d: %d\n",++Cas,bfs());
16 }
17 return 0;
18 }
19 char viss[20][20][1<<14];
20 int vis(struct point* t){
21 int ans=0,i=0;
22 if(viss[t->x][t->y][t->body])return 1;
23 viss[t->x][t->y][t->body]=1;
24 return 0;
25 }
26 char map[20][20],mapt[20][20];
27 char valid(int x,int y){
28 if(x<0||x>=N||y<0||y>=M||mapt[x][y])return 0;
29 return 1;
30 }
31 struct point Q[20*20*(1<<14)];
32 int head,tail;
33 int bfs(){
34 int x,y,lx,ly,i,k,nx,ny;
35 struct point t,now;
36 memset(viss,0,sizeof(viss));
37 scanf("%d%d",&lx,&ly);
38 t.x=lx-1;t.y=ly-1;t.dis=0;t.body=0;
39 for(i=1;i<L;++i){
40 scanf("%d%d",&x,&y);
41 for(k=0;k<4;++k)if(lx+kk[k][0]==x&&ly+kk[k][1]==y)break;
42 t.body|=k<<((i-1)<<1);
43 lx=x;ly=y;
44 }
45 memset(map,0,sizeof(map));
46 scanf("%d",&k);
47 for(i=0;i<k;++i){
48 scanf("%d%d",&x,&y);
49 map[x-1][y-1]=1;
50 }
51 head=tail=0;
52 Q[tail++]=t;
53 vis(&t);
54 while(head!=tail){
55 now=Q[head++];
56 if(now.x==0&&now.y==0)return now.dis;
57
58 memcpy(mapt,map,sizeof(map));
59 mapt[x=now.x][y=now.y]=1;
60 int s=now.body;
61 for(i=1;i<L;++i,s>>=2){
62 k=s&3;
63 mapt[x=x+kk[k][0]][y=y+kk[k][1]]=1;
64 }
65
66 for(k=0;k<4;++k){
67 if(!valid(nx=now.x+kk[k][0],ny=now.y+kk[k][1]))continue;
68 t.x=nx,t.y=ny;
69 t.body=((now.body<<2)|(3-k))&((1<<((L-1)<<1))-1);
70 t.dis=now.dis+1;
71 if(!vis(&t)){
72 Q[tail++]=t;
73 }
74 }
75 }
76 return -1;
77 }