問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3259思路:
這題的描述挺有意思，通過某些路徑可以回到過去之類，其實(shí)就是求是否存在負(fù)權(quán)回路的問題
Bellman-Ford算法的典型應(yīng)用
一個問題是，Bellman-Ford用于判斷從某個源點(diǎn)可達(dá)的負(fù)權(quán)回路，而這里求的是整個圖，而且也沒有說明該圖一定是connected的
解決上述問題的一個方法就是添加一個頂點(diǎn)，然后從該新頂點(diǎn)到每個其他頂點(diǎn)添加一條權(quán)值為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思路:
題目說的有點(diǎn)復(fù)雜，其實(shí)就是求單源最短路徑，Dijkstra算法
需要注意的是輸入可能有重邊
具體關(guān)于Dijkstra算法，參考算法導(dǎo)論，有詳細(xì)的證明
第一次寫該算法，一次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思路:
好題，枚舉 + 二分
枚舉所有可能路徑的前兩個點(diǎn)
要注意的是:
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
區(qū)別在于: "
there are already some roads between some villages"
如何在求最小生成樹的算法中體現(xiàn)某些路徑已經(jīng)存在了呢？
對于Prim算法，只要將已經(jīng)存在的路徑(u, v)的權(quán)重設(shè)置為0即可（為什么？）
對于Kruskal算法，比較容易理解，只要將已經(jīng)存在的路徑(u, v)進(jìn)行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)
現(xiàn)在，采用剪切-粘帖的方法來證明T不是一顆最小生成樹，即矛盾
將T中的最長邊(x, y)剪切掉，這樣就得到兩顆子樹
在R中，至少存在一條邊(p, q)可以將這兩顆子樹連接起來，這樣就得到:
T - (x, y) + (p, q) < T
代碼(這里采用Kruskal算法，并查集實(shí)現(xiàn))
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算法
參考算法導(dǎo)論
代碼(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總結(jié):
逆向的拓?fù)渑判颍韧趯D(zhuǎn)置圖進(jìn)行正向的拓?fù)渑判颍ㄆ鋵?shí)就是入度與出度的區(qū)別）
DFS實(shí)現(xiàn)拓?fù)渑判蜻m合于求出所有可能的解
BFS實(shí)現(xiàn)拓?fù)渑判蜻m合于求出滿足特定要求的解
代碼:
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 }
轉(zhuǎn)載:
PKU 3687 在基本的拓?fù)渑判虻幕A(chǔ)上又增加了一個要求：編號最小的節(jié)點(diǎn)要盡量排在前面；在滿足上一個條件的基礎(chǔ)上，編號第二小的節(jié)點(diǎn)要盡量排在前面；在滿足前兩個條件的基礎(chǔ)上，編號第三小的節(jié)點(diǎn)要盡量排在前面……依此類推。（注意，這和字典序是兩回事，不可以混淆。）
如圖 1 所示，滿足要求的拓?fù)湫驊?yīng)該是：6 4 1 3 9 2 5 7 8 0。
圖 1 一個拓?fù)渑判虻睦?/div>
一般來說，在一個有向無環(huán)圖中，用 BFS 進(jìn)行拓?fù)渑判蚴潜容^常見的
做法
做法，如
算法 1 所示。但是它不一定能得到本題要求的拓?fù)湫颉?br style="line-height: normal; ">
1. 把所有入度為 0 的節(jié)點(diǎn)放進(jìn)隊(duì)列 Q
2. WHILE： Q 不是空隊(duì)列
3. 從 Q 中取出隊(duì)列首元素 a，把 a 添加到答案的尾部。
4. FOR：所有從 a 出發(fā)的邊 a → b
5. 把 b 的入度減 1。如果 b 的入度變?yōu)?0，則把 b 放進(jìn)隊(duì)列 Q。 |
算法 1 用 BFS 進(jìn)行拓?fù)渑判?/div>
為了解決本問題，下面讓我來探究一下拓?fù)湫虻囊恍┬再|(zhì)。以
圖 1 為例，節(jié)點(diǎn) 0 毫無疑問排在最后。除了節(jié)點(diǎn) 0 以外，有三條互相平行的路徑：
6 →
4 →
1、
3→
9 →
2 和
5 →
7 →
8。一條路徑上的各個節(jié)點(diǎn)的先后關(guān)系都是不能改變的，比如路徑
6 →
4 →
1 上的三個節(jié)點(diǎn)在拓?fù)湫蛑校欢ㄊ?nbsp;
6 在最前，
1 在最后。但是，互相平行的各條路徑，在總的拓?fù)湫蛑?strong style="line-height: normal; ">任意交錯都是合法的。比如，以下都是
圖 1 的合法拓?fù)湫颍?br style="line-height: normal; ">
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。
怎么才能找出題目要求的拓?fù)湫蚰兀吭谶@里，我想用
字典序最先的拓?fù)湫騺硪鲞@個算法。
算法 2 可以求出字典序最先的拓?fù)湫颉?br style="line-height: normal; ">
1. 把所有入度為 0 的節(jié)點(diǎn)放進(jìn)優(yōu)先隊(duì)列 PQ
2. WHILE： PQ 不是空隊(duì)列
3. 從 PQ 中取出編號最小的元素 a，把 a 添加到答案的尾部。
4. FOR：所有從 a 出發(fā)的邊 a → b
5. 把 b 的入度減 1。如果 b 的入度變?yōu)?0，則把 b 放進(jìn)優(yōu)先隊(duì)列 PQ。 |
算法 2 求出字典序最先的拓?fù)湫?/div>
可見，
算法 2 和
算法 1 基本一樣，只是把隊(duì)列改成了優(yōu)先隊(duì)列。用它求出的
圖 1 的字典序最先的拓?fù)湫驗(yàn)椋?font color="#339900" style="line-height: normal; ">
3 5 6 4 1 7 8 9 2 0。但是這顯然不是本題要求的答案，因?yàn)楣?jié)點(diǎn) 1 的位置還不夠靠前。
算法 2 可以算是一個貪心算法，每一步都找編號最小的節(jié)點(diǎn)。但是對于
圖 1 中的三條路徑，頭的編號比較小的，不一定要先出隊(duì)列。正確的步驟應(yīng)該如下：
- 節(jié)點(diǎn) 0 的位置是鐵定在最后的，不用考慮。只考慮剩下的三條路徑。
- 先找編號最小的，節(jié)點(diǎn) 1。把它和它所在的路徑中位于它前面的節(jié)點(diǎn)全部拿出來。目前的答案是 6 4 1，這樣， 節(jié)點(diǎn) 1 就盡量靠前了。
- 再找剩下的節(jié)點(diǎn)中編號最小的，節(jié)點(diǎn) 2。把它和它所在的路徑中位于它前面的節(jié)點(diǎn)全部拿出來。目前的答案是 6 4 1 3 9 2 ，這樣，節(jié)點(diǎn) 2 就盡量靠前了。
- 只剩下一條路徑了，只能依次把其中的節(jié)點(diǎn)拿出來。最后答案就是 6 4 1 3 9 2 5 7 8 0。
顯然，
算法 2 的貪心策略對于這個問題是不可行的。不能著眼于每條路徑的頭，而是要找編號最小的節(jié)點(diǎn)在哪條路徑上，優(yōu)先把這條路徑拿出來。但問題在于，在 BFS 的過程中，我們只能看到每條路徑的頭，看不到后面的節(jié)點(diǎn)，這該怎么辦呢？
讓我們換個角度想一想，節(jié)點(diǎn) 3 和 6，應(yīng)該是 6 先出隊(duì)列，因?yàn)楣?jié)點(diǎn) 1 在 6 的后面。這和節(jié)點(diǎn) 3 和 6 的編號大小沒有任何關(guān)系。但是，再看另外兩條路徑的尾部，節(jié)點(diǎn) 2 和 8，可以肯定地說，2
一定先出隊(duì)列，因?yàn)樗鼈兒竺娑紱]有別的節(jié)點(diǎn)了，這個時候完全以這兩個節(jié)點(diǎn)本身的編號大小決定順序。歸納起來就是說，對于若干條平行的路徑，
小的頭部不一定排在前面，但是
大的尾部一定排在后面。于是，就有了
算法 3。
1. 把所有出度為 0 的節(jié)點(diǎn)放進(jìn)優(yōu)先隊(duì)列 PQ
2. WHILE： PQ 不是空隊(duì)列
3. 從 PQ 中取出編號最大的元素 a，把 a 添加到答案的頭部。
4. FOR：所有指向 a 的邊 b → a
5. 把 b 的出度減 1。如果 b 的出度變?yōu)?0，則把 b 放進(jìn)優(yōu)先隊(duì)列 PQ。 |
算法 3 求出本題目要求的拓?fù)湫?/div>
我覺得這道題目確實(shí)挺奧妙的，我搞了很久才想通
算法 3 為什么是正確的，特地在此寫一下。
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1664思路:
就是根據(jù)題意進(jìn)行DFS，要注意的是如何避免重復(fù): 所放蘋果數(shù)目遞減
居然一會就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進(jìn)行標(biāo)記，使之匹配任何字母，然后重復(fù)以上過程
不過，程序不知道該如何寫
參考discuss以及其他人思路，發(fā)現(xiàn)可以用拓?fù)渑判騺碜觯ㄍ負(fù)渑判颍瑓⒖妓惴▽?dǎo)論)
如何根據(jù)輸入來建立鄰接矩陣比較有意思，另外根據(jù)各個頂點(diǎn)的入度DFS實(shí)現(xiàn)拓?fù)渑判?br>
代碼:
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求最短路徑肯定是沒有問題的，關(guān)鍵是狀態(tài)如何表示
參考別人的思路，原來蛇身只需要通過上、下、左、右四個方向表示即可(兩bits或4進(jìn)制)，這樣可以很大程度上減少空間，而且判重也就不再是個問題，只需要用三維數(shù)組表示即可
不過我自己寫出來的代碼卻總是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 }
|
久久亚洲天堂|
久久青青草原国产精品免费|
久久久久久久久波多野高潮|
手机看片久久高清国产日韩|
久久久久久亚洲精品影院|
久久精品国产精品亚洲精品|
久久婷婷人人澡人人爽人人爱
|
日日狠狠久久偷偷色综合免费
|
国产高清国内精品福利99久久|
激情综合色综合久久综合|
久久一区二区免费播放|
久久精品国产99久久久古代
|
久久综合狠狠综合久久|
久久人人爽人人爽人人AV|
午夜天堂av天堂久久久|
精品欧美一区二区三区久久久|
欧美亚洲国产精品久久久久|
亚洲精品无码成人片久久|
91久久精品国产91性色也|
亚洲AV无码久久精品狠狠爱浪潮|
久久99精品久久久久久动态图|
久久精品国产亚洲精品|
国产99久久精品一区二区|
亚洲精品乱码久久久久久|
久久免费线看线看|
久久狠狠爱亚洲综合影院|
超级碰久久免费公开视频|
亚洲综合伊人久久大杳蕉|
久久只这里是精品66|
国产精品一久久香蕉产线看|
精品国产99久久久久久麻豆|
国产99久久久久久免费看|
99久久精品免费看国产一区二区三区|
日本三级久久网|
A级毛片无码久久精品免费
|
欧美一区二区久久精品|
久久国产视屏|
国产精久久一区二区三区|
国产精品久久久久影院嫩草|
麻豆亚洲AV永久无码精品久久
|