當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

POJ 图算法

發布時間：2025/1/21 编程问答 19 豆豆

生活随笔收集整理的這篇文章主要介紹了 POJ 图算法小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

圖的深度優先遍歷和廣度優先遍歷	poj3278, ?poj2049, poj3083
最短路徑算法	poj1860,poj3259,poj1062,poj2253,poj1125,poj2240
最小生成樹算法	poj1789,poj2485,poj1258,poj3026
拓撲排序	poj1094, poj3267(DP)，poj3687
二分圖的最大匹配	poj3041,poj3020
最大流的增廣路算法	poj1459,poj3436

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

?????????????????????????????????????

???

??????????????

圖的深度優先遍歷和廣度優先遍歷

poj3278

簡單bfs，話說要加vis滴。話說要剪枝滴。妹的TLE了好幾次！糾結啊！? 我抽了，剛才居然用bitset試了幾遍。不RE才怪。。。

渣代碼：

View Code 1 #include <iostream>
2 #include <cstring>
3 #include <cstdio>
4 #include <queue>
5
6 using namespace std;
7
8 int N, K;
9
10 class node {
11 public:
12 int p;
13 int m;
14 };
15
16 queue<node> q;
17 bool vis[200010];
18
19 void bfs(int p) {
20 while(!q.empty()) q.pop();
21 memset(vis, false, sizeof(vis));
22
23 node t, v;
24 t.p = p; t.m = 0;
25 q.push(t); vis[p] = true;
26
27 while(!q.empty()) {
28 v = q.front(); q.pop();
29
30 if(v.p == K) {printf("%d\n", v.m); return;}
31 t.m = v.m + 1;
32
33 t.p = v.p - 1;
34 if(!vis[t.p] && t.p >= 0) {
35 q.push(t); vis[t.p] = true;
36 }
37
38 if(v.p > K) continue;
39
40 t.p = v.p + 1;
41 if(!vis[t.p]) {
42 q.push(t); vis[t.p] = true;
43 }
44
45 t.p = v.p * 2;
46 if(!vis[t.p]) {
47 q.push(t); vis[t.p] = true;
48 }
49 }
50 }
51
52 int main() {
53 //freopen("data.in", "r", stdin);
54
55 while(~scanf("%d%d", &N, &K)) {
56 bfs(N);
57 }
58 return 0;
59 }

poj 2049

關于這道題，我想說。。。我想砸鍵盤！！！wa了nnnn次！后來卑鄙的看大牛的代碼過的。T_T

抄襲代碼

View Code 1 /*主要思路如下：
2 (1)首先是建圖, 由于輸入給的都是線段, 但是我們平常處理這類問題都是轉換為網格來做的, 因此需要
3 將線段轉換為網格.轉化的方法是對于每個格子,用其左上角點的坐標來表示這個格子,如果其左上角點的
4 坐標是[i][j],那么這個格子就表示為[i][j].將其四周邊界的四條線段歸這個格子管.即為每個格子建一
5 個數組round[i][j][4],第三維的四個位置分別表示這四條線段的類型: 0表示空氣,1表示墻,2表示是一扇
6 門,這樣這個模型就建立好了.
7 (2)其次是bfs的起始點選為Nemo所在的位置,注意要將這個浮點點位置轉化為格子的坐標.轉化的方法很簡
8 單.對于x坐標取整即可,對于y坐標取整+1即可,比如Nemo所在位置為[1.2, 1.3]那么轉化為格子的坐標即為:
9 [1, 2].這個坐標即位bfs遍歷的起始點
10 (3)遍歷的時候如果所走的方向是墻,則不可走.如果是門則將當前總的steps數+1,如果為空氣,steps數不變.
11 另外一點就是如何判重.判重不能簡單地記錄有沒有被訪問過,而是需要記錄到當前格子的最小步驟.如果當
12 前總步驟數小于當前格子的最小步驟數,則更新其最小步驟數并將這個格子加入隊列中.
13 (4)遍歷的終止位置即為題目中的出發位置[0, 0]*/
14
15 #include <iostream>
16 #include <cstring>
17 #include <cstdio>
18 #include <queue>
19
20 using namespace std;
21
22 const int N = 205;
23 const int inf = ~0u>>2;
24
25 struct situ {
26 int x;
27 int y;
28 int s; //到當前節所走的步數
29 int d; //d表示到當前節點來的商議個節點的方向
30 };
31
32 queue<situ> q;
33
34 int mins;
35 int g[N][N][4];
36 int st[N][N];
37 int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
38 // 0上，1下，2左，3右
39 int m, n;
40
41 bool ok(int x, int y) { //看是否越界
42 if(x < 0 || x > 199 || y < 0 || y > 199) return false;
43 return true;
44 }
45
46 void change_D(int i, int &d) { //來向要跟上一個節點的去向正好相反
47 if(i == 0) d = 1;
48 else if(i == 1) d = 0;
49 else if(i == 2) d = 3;
50 else d = 2;
51 }
52
53 void init() {
54 mins = inf;
55 for(int i = 0; i < N; ++i) {
56 for(int j = 0; j < N; ++j) {
57 st[i][j] = inf;
58 }
59 }
60 while(!q.empty()) q.pop();
61 }
62
63 void bfs(int sx, int sy) {
64 init();
65
66 situ t, v;
67 t.x = sx, t.y = sy, t.d = -1; t.s = 0;
68 st[sx][sy] = 0; q.push(t);
69
70 int x, y, d, s, i;
71 int nx, ny, nd, ns;
72 while(!q.empty()) {
73 v = q.front(); q.pop();
74 x = v.x; y = v.y; s = v.s; d = v.d;
75
76 if(x == 0 && y == 0) {
77 //printf("%d %d\n", s, mins);
78 //printf("%d\n", st[x][y]);
79 if(s < mins) mins = s;
80 continue;
81 }
82 for(i = 0; i < 4; i++) {
83 if(i == d || g[x][y][i] == 1) continue;
84 nx = x + dir[i][0];
85 ny = y + dir[i][1];
86 if(!ok(nx, ny)) continue;
87
88 change_D(i, nd);
89 if(g[x][y][i] == 2) ns = s + 1;
90 else ns = s;
91
92 if(ns < st[nx][ny] && ns < mins) {
93 st[nx][ny] = ns;
94 t.x = nx; t.y = ny; t.d = nd; t.s = ns;
95 q.push(t);
96 }
97 }
98 }
99 }
100
101 int main () {
102 //freopen("data.in", "r", stdin);
103
104 int i, j;
105 int x, y, d, t;
106 double a, b;
107 while(~scanf("%d%d", &m, &n)) {
108 if(m == -1 && n == -1) break;
109 memset(g, 0, sizeof(g));
110 for(i = 0; i < m; ++i) {
111 scanf("%d%d%d%d", &x, &y, &d, &t);
112 if(d == 1) {
113 for(j = y + 1; j <= y + t; ++j)
114 g[x][j][2] = g[x-1][j][3] = 1;
115 } else {
116 for(j = x; j < x + t; ++j)
117 g[j][y][0] = g[j][y+1][1] = 1;
118 }
119 }
120
121 for(i = 0; i < n; ++i) {
122 scanf("%d%d%d", &x, &y, &d);
123 if(d == 1) g[x][y+1][2] = g[x-1][y+1][3] = 2;
124 else g[x][y][0] = g[x][y+1][1] = 2;
125 }
126 scanf("%lf%lf", &a, &b);
127 x = a; y = b + 1;
128 if(x < 0 || x > 199 || y < 0 || y > 199) {printf("0\n"); continue;}
129 bfs(x, y);
130 if(mins == inf) printf("-1\n");
131 else printf("%d\n", mins);
132 }
133 return 0;
134 }

?poj 3083

昨天以為是一道巨復雜的模擬加搜索題。然后想各種情況。。。然后就瘋掉了。今天看了一下網上的解題報告，方向轉的真神了！Orz。

左優先時順時針，右優先時逆時針。加一個全局變量dir，控制下一步的方向。以左優先為例，這一步向上走，則下一步按順時針方向轉3次，向左走。

右優先同理。。。

關鍵代碼：

View Code 1 int Left[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
2 int Right[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
3
4 bool inMap(int x, int y) {
5 if(x < 0 || x >= h || y < 0 || y >= w) return false;
6 return true;
7 }
8
9 int dfs_l(int x, int y, int s) { //左優先
10 if(x == ei && y == ej) {
11 return s + 1;
12 }
13 if(!inMap(x, y) || map[x][y] == '#') return 0;
14 dir = (dir + 3) % 4;
15 int tmp;
16 while(1) {
17 tmp = dfs_l(x + Left[dir][0], y + Left[dir][1], s + 1);
18 if(tmp > 0) break;
19 dir = (dir + 1) % 4;
20 }
21 }

最短路徑算法

poj 1860

spfa裸模板，話說本菜以前看過的spfa都還給別人了。今天又重新看了一遍。順便寫下模板。。。

View Code 1 #include <iostream>
2 #include <cstring>
3 #include <cstdio>
4 #include <queue>
5
6 using namespace std;
7
8 const int N = 110;
9 const double inf = ~0u>>2;
10
11 struct node {
12 int from;
13 int to;
14 double c;
15 double r;
16 int next;
17 } g[N<<1];
18
19 int head[N], t;
20 bool inq[N];
21 double dis[N], sum;
22 int n, m, s;
23
24 queue<int> q;
25
26 void add(int u, int v, double r, double c) {
27 g[t].from = u; g[t].to = v; g[t].c = c; g[t].r = r;
28 g[t].next = head[u]; head[u] = t++;
29 }
30
31 void init() {
32 for(int i = 0; i < N; i++) {
33 dis[i] = 0; inq[i] = false;
34 }
35 memset(head, 0, sizeof(head)); t = 1;
36 while(!q.empty()) q.pop();
37 }
38
39 bool spfa() {
40 double c, r;
41 int u, v, i;
42 dis[s] = sum;
43 q.push(s);
44 inq[s] = true;
45
46 while(!q.empty()) {
47 u = q.front();
48 for(i = head[u]; i; i = g[i].next) {
49 v = g[i].to; c = g[i].c; r = g[i].r;
50
51 if(dis[v] < (dis[u] - c) * r) {
52 dis[v] = (dis[u] - c) * r;
53 if(!inq[v]) {
54 q.push(v);
55 inq[v] = true;
56 }
57 }
58 }
59 //printf("%d %lf\n", u, dis[u]);
60 inq[u] = false;
61 q.pop();
62 }
63 //printf("%lf %lf\n", dis[s], sum);
64 return dis[s] > sum;
65 }
66
67 int main() {
68 //freopen("data.in", "r", stdin);
69
70 int i, x, y;
71 double R, C;
72 while(~scanf("%d%d%d%lf", &n, &m, &s, &sum)) {
73 init();
74 for(i = 0; i < m; i++) {
75 scanf("%d%d%lf%lf", &x, &y, &R, &C);
76 add(x, y, R, C);
77 scanf("%lf%lf", &R, &C);
78 add(y, x, R, C);
79 }
80 if(spfa()) puts("YES");
81 else puts("NO");
82 }
83 return 0;
84 }

poj 3259

spfa判斷是否有負環，個人還是習慣用鄰接表寫spfa。。。注意有重邊，wa了一次。。

View Code 1 #include <iostream>
2 #include <cstring>
3 #include <cstdio>
4 #include <queue>
5
6 using namespace std;
7
8 const int N = 510;
9 const int M = 6000;
10 const int inf = ~0u>>2;
11
12 struct node {
13 int to;
14 int val;
15 int next;
16 } g[M];
17
18 int head[N], t;
19 int dis[N];
20 int cnt[N];
21 int d[N][N];
22 bool inq[N];
23 int n, m, w;
24 queue<int> q;
25
26 void init() {
27 while(!q.empty()) q.pop();
28 memset(head, 0, sizeof(head));
29 memset(inq, 0, sizeof(inq));
30 memset(cnt, 0, sizeof(cnt));
31 for(int i = 0; i <= n; ++i) {
32 dis[i] = inf;
33 for(int j = 0; j <= n; ++j)
34 d[i][j] = inf;
35 }
36 t = 1;
37 }
38
39 void add(int u, int v, int z) {
40 g[t].to = v; g[t].val = z; g[t].next = head[u]; head[u] = t++;
41 }
42
43 bool spfa() {
44 int i, u, v, z;
45 q.push(1); inq[1] = true;
46 dis[1] = 0; cnt[1]++;
47
48 while(!q.empty()) {
49 u = q.front();
50 for(i = head[u]; i; i = g[i].next) {
51 v = g[i].to; z = g[i].val;
52 if(dis[v] > dis[u] + z) {
53 dis[v] = dis[u] + z;
54 if(!inq[v]) {
55 cnt[v]++;
56 inq[v] = true;
57 if(cnt[v] > n) return false;
58 q.push(v);
59 }
60 }
61 }
62 inq[u] = false;
63 q.pop();
64 }
65 return true;
66 }
67
68 int main() {
69 //freopen("data.in", "r", stdin);
70
71 int f, x, y, z, i;
72 scanf("%d", &f);
73
74 while(f--) {
75
76 scanf("%d%d%d", &n, &m, &w);
77 init();
78 for(i = 0; i < m; ++i) {
79 scanf("%d%d%d", &x, &y, &z);
80 if(d[x][y] > z) d[x][y] = z;
81 else continue;
82 add(x, y, z);
83 add(y, x, z);
84 }
85 for(i = 0; i < w; ++i) {
86 scanf("%d%d%d", &x, &y, &z);
87 add(x, y, -z);
88 }
89 if(spfa()) puts("NO");
90 else puts("YES");
91 }
92 return 0;
93 }

poj 1062

這題做的想吐！！妹的建圖費勁也就算了，還得分等級！！這不是折騰人嗎！

思路是加一個源點0，0到每個點i的距離等于i點本來的價格P，然后進行n次spfa，每次限定一個等級Lv[i]，保證spfa時搜到的點j，使Lv[i] - Lv[j] <= m && Lv[j] <= Lv[i]；

關鍵代碼：

View Code 1 int spfa() { //一次spfa
2 queue<int> q;
3 int u, v, w, i;
4
5 for(i = 0; i < N; ++i) dis[i] = inf, inq[i] = false;
6 q.push(0);
7 inq[0] = true;
8 dis[0] = 0;
9
10 while(!q.empty()) {
11 u = q.front(); q.pop();
12 inq[u] = false;
13
14 for(i = 0; i < mp[u].size(); ++i) {
15 v = mp[u][i].y; w = mp[u][i].z;
16
17 if(dis[v] > dis[u] + w && L - lv[v] <= m && lv[v] <= L) {
18 dis[v] = dis[u] + w;
19 if(!inq[v]) {
20 inq[v] = true;
21 q.push(v);
22 }
23 }
24 }
25 }
26 return dis[1];
27 }
28
29 for(i = 1; i <= n; ++i) {
30 L = lv[i];
31 ans = min(ans, spfa());
32 }

poj 2253

二分 + SPFA，開始看錯題意了，上去就寫Dijkstra，后來仔細一看不是求最短路，或者說是加邊權限制的最短路，用spfa水過了。

思路：統計出所有路徑的Min和Max，以這兩個數為上下界進行二分。

C++小知識，vector型數據調用size()函數直接跟整型的i做比較編譯器會警告，最好加上static_cast<int>()，例如： for(i = 0; i < static_cast<int>(mp[u].size()); ++i) 這樣編譯器就沒話說了。哈

ps：個人感覺，遇到double就用eps，用了不會錯，不用可能錯^_^

代碼：

View Code 1 #include <iostream>
2 #include <cstring>
3 #include <cstdio>
4 #include <cmath>
5 #include <vector>
6 #include <queue>
7
8 using namespace std;
9
10 const int N = 210;
11 const double inf = ~0u>>1;
12 const double eps = 1e-6;
13
14 class Node {
15 public:
16 int v;
17 double z;
18 Node(int a, double b) : v(a), z(b) {};
19 };
20
21 vector<Node> mp[N];
22
23 double x[N], y[N];
24 double dis[N], lim;
25 bool inq[N];
26 int n;
27
28 double Dis(int i, int j) {
29 return sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]));
30 }
31
32 void init() {
33 for(int i = 0; i < N; ++i) {
34 x[i] = y[i] = 0;
35 mp[i].clear();
36 }
37 }
38
39 bool spfa() {
40 queue<int> q;
41 int i, u, v;
42 double w;
43 for(i = 0; i < N; ++i) {
44 dis[i] = inf; inq[i] = false;
45 }
46 dis[0] = 0; inq[0] = true;
47 q.push(0);
48
49 while(!q.empty()) {
50 u = q.front(); inq[u] = false; q.pop();
51
52 for(i = 0; i < static_cast<int>(mp[u].size()); ++i) {
53 v = mp[u][i].v; w = mp[u][i].z;
54
55 if(dis[v] > dis[u] + w && w <= lim) {
56 dis[v] = dis[u] + w;
57 if(!inq[v]) {
58 inq[v] = true;
59 q.push(v);
60 }
61 }
62 }
63 }
64 if(dis[1] < inf) return true;
65 else return false;
66 }
67
68 int main() {
69 //freopen("data.in", "r", stdin);
70
71 int i, j, cas = 0;
72 double t, l, r;
73 while(scanf("%d", &n), n) {
74 init();
75 scanf("%lf%lf", &x[0], &y[0]);
76 l = inf; r = -1;
77 for(i = 1; i < n; ++i) {
78 scanf("%lf%lf", x + i, y + i);
79 for(j = 0; j < i; ++j) {
80 t = Dis(i, j);
81 l = min(t, l); r = max(t, r);
82 mp[i].push_back(Node(j, t));
83 mp[j].push_back(Node(i, t));
84 // printf("%d %d %lf\n", i, j, t);
85 }
86 }
87
88 while(1) {
89 if(!(r - l > eps)) break;
90 lim = (l + r) / 2;
91
92 if(spfa()) r = lim;
93 else l = lim;
94 }
95 printf("Scenario #%d\nFrog Distance = %.3f\n", ++cas, l);
96 putchar('\n');
97 }
98 return 0;
99 }

poj 1125

用floyd掃一遍，然后找開始節點和最大長度

poj 2240

把思路想錯了，結果好幾次TLE，以每一種貨幣為始點進行spfa，如果出現始點第二次入隊列，說明已經有利潤，dis[]初始化為0

渣代碼：

View Code 1 #include <iostream>
2 #include <cstring>
3 #include <cstdio>
4 #include <string>
5
6 using namespace std;
7
8 const int N = 50;
9 const double eps = 1e-6;
10
11 string ts[N];
12
13 struct node {
14 int v;
15 double w;
16 int next;
17 }g[N*N];
18
19 int head[N], t, n;
20 double dis[N];
21 int q[N<<11];
22 bool inq[N];
23
24 int findp(string t) {
25 int i;
26 for(i = 0; i < n; ++i) {
27 if(t == ts[i]) return i;
28 }
29 return -1;
30 }
31
32 void init() {
33 memset(head, 0, sizeof(head));
34 for(int i = 0; i < N; ++i) ts[i].clear();
35 t = 1;
36 }
37
38 void add(int u, int v, double w) {
39 g[t].v = v; g[t].w = w; g[t].next = head[u]; head[u] = t++;
40 }
41
42 bool spfa(int s) {
43 int i, u, v, f = 0, r = 0;
44 double w;
45
46 for(i = 0; i < N; ++i) {
47 dis[i] = 0; inq[i] = false;
48 q[i] = 0;
49 }
50 q[r++] = s; inq[s] = true; dis[s] = 1;
51
52 while(f < r) {
53 u = q[f]; f++; inq[u] = false;
54
55 for(i = head[u]; i; i = g[i].next) {
56 v = g[i].v; w = g[i].w;
57 if(dis[u] * w - dis[v] > eps) {
58 dis[v] = dis[u] * w;
59 if(!inq[v]) {
60 inq[v] = true;
61 if(v == s) return true;
62 q[r++] = v;
63 }
64 }
65 }
66
67 }
68 return false;
69 }
70
71 int main() {
72 //freopen("data.in", "r", stdin);
73
74 int m, i, x, y, cas = 0;
75 double rate;
76 string t1, t2;
77 while(scanf("%d", &n), n) {
78 init();
79 for(i = 0; i < n; ++i) {
80 cin >> ts[i];
81 }
82 scanf("%d", &m);
83 bool flag = false;
84 while(m--) {
85 cin >> t1 >> rate >> t2;
86 x = findp(t1); y = findp(t2);
87 if(x == y && rate - 1 > eps) flag = true;
88 if(!flag) add(x, y, rate);
89 //printf("%d %d %lf\n", x, y, rate);
90 }
91 printf("Case %d: ", ++cas);
92 if(flag) {puts("Yes"); continue;}
93
94 for(i = 0; i < n; ++i) {
95 if(spfa(i)) {puts("Yes"); flag = true; break;}
96 }
97 if(!flag) puts("No");
98 }
99 return 0;
100 }

最小生成樹算法

poj 1789

以前做過這道題，是用prim做的，本來以為這題用kruskal做會快一些，妹的！沒想到G++ TLE，C++ 1000+ms。。。

poj 2485

額看錯題意了。。。神啊！是讓求最小生成樹上最長的一條邊，不是保證最長邊最小構成最小生成樹。

poj 1258

裸prim，沒有看題，看數據猜過去的，把poj2485的改改就行。

poj 3026

題意很費解，我是到網上搜的思路。大概是給一個圖，然后給一些S， A0， A1， A2。。。。求每一對（S，A1），（A0， A2）等兩兩間的距離，建圖。然后求最小生成樹。

可以用bfs先把兩兩間的距離搜出來，然后就是套MST模板了。

貼代碼（建圖是參考大牛的）：

View Code 1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 #include <queue>
6
7 using namespace std;
8
9 const int N = 110;
10 const int inf = ~0u>>2;
11
12 struct Node {
13 int x;
14 int y;
15 int w;
16 Node(int a = 0, int b = 0, int c = 0) : x(a), y(b), w(c) {};
17 };
18
19 char map[N][N];
20
21 int mp[N][N];
22 int g[N][N];
23 int low[N];
24
25 bool vis[N][N];
26 bool f[N];
27 int x, y, n;
28
29 int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
30
31 void bfs(int si, int sj) {
32 int i;
33 memset(vis, 0, sizeof(vis));
34 queue<Node> q;
35
36 vis[si][sj] = true;
37 q.push(Node(si, sj, 0));
38
39 Node u, v;
40 while(!q.empty()) {
41 u = q.front(); q.pop();
42
43 for(i = 0; i < 4; ++i) {
44 v.x = u.x + dir[i][0];
45 v.y = u.y + dir[i][1];
46
47 if(!vis[v.x][v.y] && mp[v.x][v.y] >= -1) {
48 v.w = u.w + 1;
49 vis[v.x][v.y] = true;
50
51 if(mp[v.x][v.y] >= 0) {
52 //printf("%d %d %d ** %d %d\n", mp[si][sj], mp[v.x][v.y], v.w, si, sj);
53 g[mp[si][sj]][mp[v.x][v.y]] = v.w;
54 }
55 q.push(v);
56 }
57 }
58 }
59 }
60
61 int prim() {
62 int i, j, min, flag, sum = 0;
63 for(i = 0; i < n; ++i) {
64 low[i] = g[0][i]; f[i] = false;
65 }
66
67 f[0] = true; low[0] = 0;
68
69 for(i = 1; i < n; ++i) {
70 min = inf; flag = 0;
71
72 for(j = 1; j < n; ++j) {
73 if(min > low[j] && !f[j]) {
74 min = low[j];
75 flag = j;
76 }
77 }
78
79 f[flag] = true;
80 sum += low[flag];
81
82 for(j = 1; j < n; ++j) {
83 if(g[flag][j] < low[j] && !f[j]) {
84 low[j] = g[flag][j];
85 }
86 }
87 }
88 return sum;
89 }
90
91 int main() {
92 //freopen("data.in", "r", stdin);
93
94 int t, i, j;
95 char buffer[N];
96 scanf("%d", &t);
97 while(t--) {
98 scanf("%d%d", &x, &y); gets(buffer); //這里discuss里邊有講，貌似是后臺數據的問題
99 n = 0;
100 for(i = 0; i < y; ++i) {
101 gets(map[i]);
102 for(j = 0; j < x; ++j) {
103 switch (map[i][j]) {
104 case '#': mp[i][j] = -2; break;
105 case ' ': mp[i][j] = -1; break;
106 case 'A':
107 case 'S': mp[i][j] = n++; break;
108 }
109 }
110 }
111 /*for(i = 0; i < y; ++i) {
112 for(j = 0; j < x; ++j)
113 printf("%3d", mp[i][j]);
114 cout << endl;
115 }*/
116 for(i = 0; i < y; ++i) {
117 for(j = 0; j < x; ++j) {
118 if(mp[i][j] >= 0)
119 bfs(i, j);
120 }
121 }
122 /*for(i = 0; i < n; ++i) {
123 for(j = 0; j < n; ++j) {
124 printf("%d ", g[i][j]);
125 }
126 cout << endl;
127 }*/
128 printf("%d\n", prim());
129 }
130 return 0;
131 }

拓撲排序

poj 1094

每讀入一組數據進行一次toposort，如果toposort過程中出現沒有入度為0的點，則說明“Inconsistency found after xxx relations."如果一直存在多個入度為0的點，則說明"Sorted sequence cannot be determined."。否則，則為有解的情況，記錄并出去可行解就可以。

ps：今天感覺好累。

渣代碼：

View Code 1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4
5 using namespace std;
6
7 const int N = 30;
8
9 int deg[N], cnt[N];
10 int g[N][N], ans[N], n;
11
12 int toposort() {
13 int i, j, u, num, t = 0;
14 bool flag;
15 for(i = 0; i < n; ++i) {
16 cnt[i] = deg[i];
17 //printf("%d ", cnt[i]);
18 }
19 //cout << endl;
20 flag = false;
21 memset(ans, 0, sizeof(ans));
22 for(i = 0; i < n; ++i) {
23 num = 0;
24 for(j = 0; j < n; j++) {
25 if(cnt[j] == 0) {
26 u = j;
27 num++;
28 }
29 }
30 //printf("%d\n", num);
31 if(num == 0) return 0;
32 if(num > 1) flag = true;
33 cnt[u] = -1; ans[t++] = u;
34 for(j = 0; j < n; ++j) {
35 if(g[u][j]) {
36 cnt[j]--;
37 }
38 }
39 }
40 if(flag) return -1;
41 return 1;
42 }
43
44 int main() {
45 //freopen("data.in", "r", stdin);
46
47 int m, i, j, x, y, r;
48 bool f;
49 char s[N];
50
51 while(~scanf("%d%d", &n, &m)) {
52 if(n + m == 0) break;
53 f = false;
54 memset(deg, 0, sizeof(deg));
55 memset(g, false, sizeof(g));
56 for(i = 0; i < m; ++i) {
57 scanf("%s", s);
58 x = s[0] - 'A';
59 y = s[2] - 'A';
60 if(f) continue;
61 deg[y]++;
62 g[x][y] = true;
63 r = toposort();
64 if(r == 0) {
65 printf("Inconsistency found after %d relations.\n", i + 1);
66 f = true;
67 }
68 if(r == 1) {
69 printf("Sorted sequence determined after %d relations: ", i + 1);
70 for(j = 0; j < n; ++j) printf("%c", ans[j] + 'A');
71 printf(".\n");
72 f = true;
73 }
74 }
75 if(!f) puts("Sorted sequence cannot be determined.");
76 }
77 return 0;
78 }

poj 3267

這是道DP的題，以前做過。詳見http://www.cnblogs.com/vongang/archive/2011/10/06/2200131.html#

二分圖的最大匹配

poj 3687

很裸的最小點覆蓋，直接按G[a][b+1] = true;建圖。

poj 3020

最大獨立集的變形，把一維的編程二維的了。

思路是出現*的坐標標為true，然后一每個為true的坐標為起點用匈利亞算法確定是否有增廣路存在。注意，這樣統計出來的數據是最大二分匹配的二倍，因為默認的看成了無向圖。

result = 為true的結點數 - 最大二分匹配。

View Code #include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 50;

bool g[N][N];
bool usd[N][N];
int lx[N][N], ly[N][N];
int h, w;
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

bool can(int x, int y) {
int a, b, i;
for(i = 0; i < 4; ++i) {
a = x + dir[i][0];
b = y + dir[i][1];
if(!usd[a][b] && g[a][b]) {
usd[a][b] = true;
if((lx[a][b] == -1 && ly[a][b] == -1) || can(lx[a][b], ly[a][b])) {
lx[a][b] = x;
ly[a][b] = y;
return true;
}
}
}
return false;
}

int main() {
//freopen("data.in", "r", stdin);

int i, j, t;
int n, cnt;
char c;
scanf("%d", &t);
while(t--) {
scanf("%d%d", &h, &w);
getchar();
memset(g, false, sizeof(g));
for(n = 0, i = 1; i <= h; ++i) {
for(j = 1; j <= w; ++j) {
scanf("%c", &c);
//printf("%c", c);
if(c == '*') {g[i][j] = true; n++;}
// printf("%d", g[i][j]);
}
getchar();
// cout << endl;
}
cnt = 0;
memset(lx, -1, sizeof(lx));
memset(ly, -1, sizeof(ly));
for(i = 1; i <= h; ++i) {
for(j = 1; j <= w; ++j) {
if(g[i][j]) {
memset(usd, 0, sizeof(usd));
if(can(i, j)) cnt++;
}
}
}
printf("%d\n", n - cnt/2);
}
return 0;
}

最大流的增廣路算法

poj 1459

所有的p連向源點，所有的c連向匯點。以前用EK寫過，1600+ms，今天用Dinic寫的。420+ms。Dinic的優化很明顯，呵呵

View Code #include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

const int N = 110;
const int inf = ~0u>>1;

int g[N][N];
int layer[N];
bool vis[N];
int S, T;

bool Layer() {
queue<int> q;
memset(layer, -1, sizeof(layer));
q.push(S); layer[S] = 1;

int i, v;
while(!q.empty()) {
v = q.front(); q.pop();
for(i = 0; i <= T; ++i) {
if(g[v][i] && layer[i] == -1) {
layer[i] = layer[v] + 1;
if(i == T) {for(;!q.empty(); q.pop()); return true;}
q.push(i);
}
}
}
return false;
}

int Dinic() {
deque<int> q;
int i, v, p;
int vs, ve, Min, sum = 0;

while(Layer()) {
memset(vis, 0, sizeof(vis));
q.push_back(S);
vis[S] = true;

while(!q.empty()) {
v = q.back();
if(v != T) {
for(i = 0; i <= T; ++i) {
if(g[v][i] && !vis[i] && layer[i] == layer[v] + 1) {
vis[i] = true;
q.push_back(i); break;
}
}
if(i > T) q.pop_back();
} else {
Min = inf;
for(i = 1; i < static_cast<int>(q.size()); ++i) {
vs = q[i-1]; ve = q[i];
if(g[vs][ve] && Min > g[vs][ve]) {
Min = g[vs][ve];
p = vs;
}
}
sum += Min;
for(i = 1; i < static_cast<int>(q.size()); ++i) {
vs = q[i-1]; ve = q[i];
if(g[vs][ve]) {
g[vs][ve] -= Min;
g[ve][vs] += Min;
}
}
while(!q.empty() && q.back() != p) {
vis[q.back()] = false;
q.pop_back();
}
}
}
}
return sum;
}

int main() {
//freopen("data.in", "r", stdin);

int n, np, nc, m, x, y, z;
char t;
while(~scanf("%d%d%d%d", &n, &np, &nc, &m)) {
S = 0; T = n + 1;
memset(g, 0, sizeof(g));
while(m--) {
cin >> t >> x >> t >> y >> t >> z;
//printf("%d %d %d\n", x, y, z);
g[x + 1][y + 1] = z;
}
while(np--) {
cin >> t >> x >> t >> z;
//printf("%d %d\n", x, z);
g[S][x + 1] = z;
}
while(nc--) {
cin >> t >> x >> t >> z;
//printf("%d %d %d\n", x + 1, T, z);
g[x + 1][T] = z;
}
/*for(int i = 0; i <= T; ++i) {
for(int j = 0; j <= T; ++j) {
printf("%d ", g[i][j]);
}
cout << endl;
}*/
printf("%d\n", Dinic());
}
return 0;
}

總結

以上是生活随笔為你收集整理的POJ 图算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

算法
POJ

上一篇： windows server 2003之
下一篇：某android平板项目开发笔记--自定