問題:
http://poj.org/problem?id=2312思路:
這題糾結(jié)了...一上午都沒寫出來，原以為很簡(jiǎn)單的(其實(shí)，很多人都說是簡(jiǎn)單題，艾)
首先想到的是廣搜，因?yàn)槭乔髲脑袋c(diǎn)到目的地的最小步數(shù)嘛，典型的BFS，結(jié)果卻始終不知道如何表示每個(gè)狀態(tài)以及狀態(tài)間的判重
既然廣搜不會(huì)，那就深搜吧，恩，很快就寫出代碼，結(jié)果TLE...
無奈，只好在網(wǎng)上找解法，發(fā)現(xiàn)一種相當(dāng)不錯(cuò)的BFS代碼:
隊(duì)列的狀態(tài)只需要保存當(dāng)前位置即可，另外用數(shù)組best[][]表示目前從源點(diǎn)到達(dá)每個(gè)點(diǎn)的最小步數(shù)
在從當(dāng)前點(diǎn)擴(kuò)展的時(shí)候，只將有最小步數(shù)更新的點(diǎn)加入隊(duì)列
這樣當(dāng)BFS搜索結(jié)束時(shí)，每個(gè)best[i][j]都保存了從源點(diǎn)到點(diǎn)[i][j]的最短步數(shù)
原來還有這樣寫B(tài)FS的方法，又學(xué)習(xí)了(*^__^*) 嘻嘻……
上述算法有點(diǎn)類似于求最短路徑呵呵
而，事實(shí)上，這題是可以很容易轉(zhuǎn)化成圖論求單源最短路徑的
代碼:
1 /* 32MS */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_LEN 301
6 #define QUEUE_SIZE 90001
7 #define INF 0x7FFFFFFF
8 #define is_valid(x, y) ((x)>=0 && (x)<M && (y)>=0 && (y)<N)
9 char map[MAX_LEN][MAX_LEN];
10 const int dx[] = {0, 0, -1, 1};
11 const int dy[] = {-1, 1, 0, 0};
12 int M, N;
13 int you_x, you_y, target_x, target_y;
14 int best[MAX_LEN][MAX_LEN]; /* important, best[i][j] stores the current 'best solution' at map[i][j] */
15 struct Node {
16 int x, y;
17 } queue[QUEUE_SIZE];
18
19 int
20 bfs()
21 {
22 int i, next_x, next_y, cur, head, tail;
23 struct Node node;
24 head = -1;
25 tail = 0;
26 queue[tail].x = you_x;
27 queue[tail].y = you_y;
28 best[you_x][you_y] = 0;
29 while(head < tail) {
30 ++head;
31 cur = best[queue[head].x][queue[head].y];
32 for(i=0; i<4; i++) {
33 node.x = queue[head].x + dx[i];
34 node.y = queue[head].y + dy[i];
35 if(is_valid(node.x, node.y)) {
36 /* excellent, only push node which can be updated in 'best' into the queue */
37 if(map[node.x][node.y] == 'E' || map[node.x][node.y] == 'T') {
38 if(best[node.x][node.y] > cur+1) {
39 best[node.x][node.y] = cur+1;
40 ++tail;
41 queue[tail] = node;
42 }
43 } else if(map[node.x][node.y] == 'B') {
44 if(best[node.x][node.y] > cur+2) {
45 best[node.x][node.y] = cur+2;
46 ++tail;
47 queue[tail] = node;
48 }
49 }
50 }
51 }
52 }
53 }
54
55 int
56 main(int argc, char **argv)
57 {
58 int i, j;
59 while(scanf("%d %d", &M, &N)!=EOF && M && N) {
60 for(i=0; i<M; i++) {
61 scanf("%s", map[i]);
62 for(j=0; j<N; j++) {
63 if(map[i][j] == 'Y') {
64 you_x = i;
65 you_y = j;
66 } else if(map[i][j] == 'T') {
67 target_x = i;
68 target_y = j;
69 }
70 best[i][j] = INF;
71 }
72 }
73 bfs();
74 printf("%d\n", best[target_x][target_y]==INF ? -1 : best[target_x][target_y]);
75 }
76 }
問題:
http://poj.org/problem?id=3561思路:
簡(jiǎn)單題，結(jié)果卻WA了一次
注意題目中給出的定義:
in adjacent cells就是說，這些符號(hào)必須是連續(xù)的，否則就要算兩個(gè)
另一點(diǎn)就是符號(hào)'\'需要寫成'\\'，開始編譯錯(cuò)誤了呵呵
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 101
5 #define is_valid(x, y) ((x)>=0 && (x)<N && (y)>=0 && (y)<M)
6 int N, M;
7 char image[MAX_LEN][MAX_LEN];
8 int visited[MAX_LEN][MAX_LEN];
9 int hor, vert, diag;
10
11 void
12 mark(int i, int j, int dx, int dy, char ch)
13 {
14 while(is_valid(i+dx, j+dy) && image[i+dx][j+dy]==ch) {
15 visited[i+dx][j+dy] = 1;
16 i += dx;
17 j += dy;
18 }
19 }
20
21 void
22 solve()
23 {
24 int i, j;
25 char ch;
26 for(i=0; i<N; i++) {
27 for(j=0; j<M; j++) {
28 ch = image[i][j];
29 if(ch!='.' && !visited[i][j]) {
30 visited[i][j] = 1;
31 switch(ch) {
32 case '-':
33 ++hor;
34 mark(i, j, 0, -1, ch);
35 mark(i, j, 0, 1, ch);
36 break;
37 case '|':
38 ++vert;
39 mark(i, j, -1, 0, ch);
40 mark(i, j, 1, 0, ch);
41 break;
42 case '\\':
43 ++diag;
44 mark(i, j, 1, 1, ch);
45 mark(i, j, -1, -1, ch);
46 break;
47 case '/':
48 ++diag;
49 mark(i, j, 1, -1, ch);
50 mark(i, j, -1, 1, ch);
51 break;
52 }
53 }
54 }
55 }
56 }
57
58 int
59 main(int argc, char **argv)
60 {
61 int i, tests;
62 scanf("%d", &tests);
63 while(tests--) {
64 scanf("%d %d", &N, &M);
65 for(i=0; i<N; i++)
66 scanf("%s", image[i]);
67 memset(visited, 0, sizeof(visited));
68 hor = vert = diag = 0;
69 solve();
70 if(hor+vert+diag == 1)
71 printf("CORRECT\n");
72 else
73 printf("INCORRECT\n");
74 }
75 }
問題:
http://poj.org/problem?id=1010思路:
題目比較難理解，解題的話就是DFS
整整花了我一個(gè)晚上，終于AC了，(*^__^*) 嘻嘻……
雖然時(shí)間花了挺久，雖然自己的解法時(shí)間需要500+MS，雖然存在其他更優(yōu)的解法，雖然......，但還是相當(dāng)有成就感，完全是我自己寫出來的
如果這題放在5個(gè)月之前，估計(jì)完全不知道怎么去寫
在沒AC之前，我一直想著自己還是原來那么菜，現(xiàn)在，至少可以說，比5個(gè)月之前的我已經(jīng)強(qiáng)了
繼續(xù)努力，F(xiàn)ighting...
代碼:
1 /* 388K 547MS */
2 #include<stdio.h>
3 #include<string.h>
4 #include<stdlib.h>
5 #define MAX_LEN 65 /* maximum number of different types of stamps */
6 #define UPPER 4 /* maximum number of stamps */
7 int types, stamps[MAX_LEN];
8 int request;
9 int maxdf, minusd, high, tie, exist, mark[MAX_LEN], ans[MAX_LEN];
10
11 int
12 compare(const void *arg1, const void *arg2)
13 {
14 return (*(int *)arg1)-(*(int *)arg2);
15 }
16
17 void
18 output()
19 {
20 int i, j;
21 if(!exist) {
22 printf("%d ---- none\n", request);
23 return;
24 }
25 printf("%d (%d): ", request, maxdf);
26 if(tie)
27 printf("tie\n");
28 else {
29 for(i=0; i<types; i++)
30 for(j=0; j<ans[i]; j++)
31 printf("%d ", stamps[i]);
32 printf("\n");
33 }
34 }
35
36 void
37 dfs(int remain, int index, int curdf, int curusd, int curhigh)
38 {
39 int i, flag = 0;
40 if(remain == 0) {
41 if(curdf < maxdf)
42 return;
43 /* satisfy the conditions: UPDATE */
44 if((curdf>maxdf) || (curdf==maxdf&&curusd<minusd) || (curdf==maxdf&&curusd==minusd&&curhigh>high)) {
45 maxdf = curdf;
46 minusd = curusd;
47 high = curhigh;
48 exist = 1;
49 tie = 0; /* remember reset 'tie' */
50 memcpy(ans, mark, sizeof(int)*MAX_LEN); /* copy the current best to 'ans' */
51 return;
52 }
53 /* TIE occurred */
54 if(curdf==maxdf && curusd==minusd && curhigh==high) {
55 tie = 1;
56 return;
57 }
58 return;
59 }
60 /* still exist several stamps unmarked */
61 for(i=index; i<types; i++) { /* Attention: i starts from 'index', which avoid duplicates such as '1 3' and '3 1' */
62 if(!mark[i] && stamps[i]<=remain && curusd+1<=UPPER) {
63 ++mark[i];
64 flag = 1;
65 dfs(remain-stamps[i], i+1, curdf+1, curusd+1, stamps[i]);
66 --mark[i];
67 }
68 }
69 /* all available stamps have been marked */
70 if(!flag) {
71 for(i=types-1; i>=0; i--) {
72 if(stamps[i]<=remain && curusd+1<=UPPER) {
73 ++mark[i];
74 dfs(remain-stamps[i], 0, curdf, curusd+1, curhigh);
75 --mark[i];
76 }
77 }
78 }
79 }
80
81 int
82 main(int argc, char **argv)
83 {
84 while(1) {
85 types = 0;
86 if(scanf("%d", &stamps[types]) == EOF)
87 break;
88 ++types;
89 while(scanf("%d", &stamps[types]) && stamps[types])
90 ++types;
91 qsort(stamps, types, sizeof(int), compare); /* ascent order */
92
93 while(scanf("%d", &request) && request) { /* each request */
94 maxdf = high = 0;
95 minusd = MAX_LEN+1;
96 exist = tie = 0;
97 memset(mark, 0, sizeof(mark));
98 dfs(request, 0, 0, 0, 0);
99 output();
100 }
101 }
102 return 0;
103 }
問題:
http://poj.org/problem?id=2060思路:
將每一個(gè)Taxi訂單作為頂點(diǎn)，根據(jù)題意如果訂單i與訂單j可以在規(guī)定時(shí)間內(nèi)到達(dá)，那么說頂點(diǎn)i與頂點(diǎn)j存在一條邊
最小路徑覆蓋問題可以轉(zhuǎn)化為最大匹配問題
見:
http://www.shnenglu.com/Joe/archive/2010/10/21/130676.html代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 501
5 #define Abs(a) ((a)>=0 ? (a) : (a)*(-1))
6 int M;
7 int graph[MAX_LEN][MAX_LEN];
8 int state[MAX_LEN], fwd[MAX_LEN], bwd[MAX_LEN];
9 struct Taxi {
10 int hour, minu;
11 int sx, sy, dx, dy;
12 }rides[MAX_LEN];
13
14 int
15 reachable(struct Taxi *fst, struct Taxi *scd)
16 {
17 int h, m;
18 h = fst->hour;
19 m = fst->minu + Abs(fst->dx-fst->sx) + Abs(fst->dy-fst->sy) + Abs(scd->sx-fst->dx) + Abs(scd->sy-fst->dy);
20 h = (h+m/60);
21 m = m%60;
22 if(h >= 24)
23 return 0;
24 if(h == scd->hour)
25 return (m<scd->minu);
26 return (h<scd->hour);
27 }
28
29 void
30 build_graph()
31 {
32 int i, j;
33 memset(graph, 0, sizeof(graph));
34 for(i=0; i<M; i++)
35 for(j=i+1; j<M; j++)
36 if(reachable(rides+i, rides+j))
37 graph[i][j] = 1;
38 }
39
40 int
41 find_path(int u)
42 {
43 int i;
44 for(i=0; i<M; i++) {
45 if(graph[u][i] && !state[i]) {
46 state[i] = 1;
47 if(bwd[i]==-1 || find_path(bwd[i])) {
48 bwd[i] = u;
49 fwd[u] = i;
50 return 1;
51 }
52 }
53 }
54 return 0;
55 }
56
57 int
58 MaxMatch()
59 {
60 int i, ans = 0;
61 memset(fwd, -1, sizeof(fwd));
62 memset(bwd, -1, sizeof(bwd));
63 for(i=0; i<M; i++) {
64 if(fwd[i] == -1) {
65 memset(state, 0, sizeof(state));
66 if(find_path(i))
67 ++ans;
68 }
69 }
70 return ans;
71 }
72
73 int
74 main(int argc, char **argv)
75 {
76 int i, tests;
77 scanf("%d", &tests);
78 while(tests--) {
79 scanf("%d", &M);
80 for(i=0; i<M; i++)
81 scanf("%d:%d %d %d %d %d", &rides[i].hour, &rides[i].minu, &rides[i].sx, &rides[i].sy, &rides[i].dx, &rides[i].dy);
82 build_graph();
83 printf("%d\n", M-MaxMatch());
84 }
85 }
在一個(gè)ＰＸＰ的有向圖中，路徑覆蓋就是在圖中找一些路經(jīng)，使之覆蓋了圖中的所有頂點(diǎn)，且任何一個(gè)頂點(diǎn)有且只有一條路徑與之關(guān)聯(lián)；（如果把這些路徑中的每條路徑從它的起始點(diǎn)走到它的終點(diǎn)，那么恰好可以經(jīng)過圖中的每個(gè)頂點(diǎn)一次且僅一次）；如果不考慮圖中存在回路，那么每每條路徑就是一個(gè)弱連通子集．
由上面可以得出：
１.一個(gè)單獨(dú)的頂點(diǎn)是一條路徑；
２．如果存在一路徑p1,p2,......pk，其中p1 為起點(diǎn)，pk為終點(diǎn)，那么在覆蓋圖中，頂點(diǎn)p1,p2,......pk不再與其它的頂點(diǎn)之間存在有向邊．
最小路徑覆蓋就是找出最小的路徑條數(shù)，使之成為Ｐ的一個(gè)路徑覆蓋．
路徑覆蓋與二分圖匹配的關(guān)系：
最小路徑覆蓋＝｜Ｐ｜－最大匹配數(shù)；
其中最大匹配數(shù)的求法是把Ｐ中的每個(gè)頂點(diǎn)pi分成兩個(gè)頂點(diǎn)pi'與pi''，如果在p中存在一條pi到pj的邊，那么在二分圖Ｐ＇中就有一條連接pi'與pj''的無向邊；這里pi' 就是p中pi的出邊，pj''就是p中pj 的一條入邊；
對(duì)于公式：最小路徑覆蓋＝｜Ｐ｜－最大匹配數(shù)；可以這么來理解；
如果匹配數(shù)為零，那么Ｐ中不存在有向邊，于是顯然有：
最小路徑覆蓋＝｜Ｐ｜－最大匹配數(shù)＝｜Ｐ｜－０＝｜Ｐ｜；即Ｐ的最小路徑覆蓋數(shù)為｜Ｐ｜；
Ｐ＇中不在于匹配邊時(shí)，路徑覆蓋數(shù)為｜Ｐ｜；
如果在Ｐ＇中增加一條匹配邊pi'－－＞pj''，那么在圖P的路徑覆蓋中就存在一條由pi連接pj的邊，也就是說pi與pj 在一條路徑上，于是路徑覆蓋數(shù)就可以減少一個(gè)；
如此繼續(xù)增加匹配邊，每增加一條，路徑覆蓋數(shù)就減少一條；直到匹配邊不能繼續(xù)增加時(shí)，路徑覆蓋數(shù)也不能再減少了，此時(shí)就有了前面的公式；但是這里只 是說話了每條匹配邊對(duì)應(yīng)于路徑覆蓋中的一條路徑上的一條連接兩個(gè)點(diǎn)之間的有向邊；下面來說明一個(gè)路徑覆蓋中的每條連接兩個(gè)頂點(diǎn)之間的有向邊對(duì)應(yīng)于一條匹配 邊；
與前面類似，對(duì)于路徑覆蓋中的每條連接兩個(gè)頂點(diǎn)之間的每條有向邊pi--->pj，我們可以在匹配圖中對(duì)應(yīng)做一條連接pi'與pj''的邊， 顯然這樣做出來圖的是一個(gè)匹配圖（這一點(diǎn)用反證法很容易證明，如果得到的圖不是一個(gè)匹配圖，那么這個(gè)圖中必定存在這樣兩條邊 pi'---pj'' 及 pi' ----pk''，（j!=k），那么在路徑覆蓋圖中就存在了兩條邊pi-->pj, pi--->pk ，那邊從pi出發(fā)的路徑就不止一條了，這與路徑覆蓋圖是矛盾的；還有另外一種情況就是存在pi'---pj'',pk'---pj''，這種情況也類似可證）；
至此，就說明了匹配邊與路徑覆蓋圖中連接兩頂點(diǎn)之間邊的一一對(duì)應(yīng)關(guān)系，那么也就說明了前面的公式成立！
問題:
http://poj.org/problem?id=2536思路:
典型的最大二分匹配，也是咱的第一道最大二分匹配
根據(jù)題意，在規(guī)定的時(shí)間和速度下，gopher[i]能夠到達(dá)hole[j]，那么在i與j之間存在一條邊，這樣就建立了二分圖
學(xué)習(xí)了匈牙利算法，見
http://www.shnenglu.com/Joe/archive/2010/10/20/130573.html代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #include<math.h>
5 #define MAX_LEN 101
6 int map[MAX_LEN][MAX_LEN];
7 int result[MAX_LEN]; /* previous matching */
8 int state[MAX_LEN];
9 int n, m, s, v;
10 struct Coordinate {
11 float x, y;
12 }gophers[MAX_LEN], holes[MAX_LEN];
13
14 int
15 findpath(int u)
16 {
17 int i;
18 for(i=0; i<m; i++) {
19 if(map[u][i] && state[i]==-1) {
20 state[i] = 1;
21 if(result[i]==-1 || findpath(result[i])) {
22 result[i] = u; /* 取反 */
23 return 1;
24 }
25 }
26 }
27 return 0;
28 }
29
30 int
31 MaxMatch()
32 {
33 int i, ans = 0;
34 for(i=0; i<n; i++) {
35 memset(state, -1, sizeof(state));
36 if(findpath(i))
37 ++ans;
38 }
39 return ans;
40 }
41
42 int
43 main(int argc, char **argv)
44 {
45 int i, j;
46 while(scanf("%d %d %d %d", &n, &m, &s, &v) != EOF) {
47 for(i=0; i<n; i++)
48 scanf("%f %f", &gophers[i].x, &gophers[i].y);
49 for(j=0; j<m; j++)
50 scanf("%f %f", &holes[j].x, &holes[j].y);
51
52 memset(map, 0, sizeof(map));
53 memset(result, -1, sizeof(result));
54 for(i=0; i<n; i++)
55 for(j=0; j<m; j++) {
56 if(sqrt((holes[j].x-gophers[i].x)*(holes[j].x-gophers[i].x) + (holes[j].y-gophers[i].y)*(holes[j].y-gophers[i].y)) <= v*s) /*reachable*/
57 map[i][j] = 1;
58 else
59 map[i][j] = 0;
60 }
61
62 printf("%d\n", n-MaxMatch());
63 }
64 }
二分圖指的是這樣一種圖：其所有的頂點(diǎn)分成兩個(gè)集合M和N，其中M或N中任意兩個(gè)在同一集合中的點(diǎn)都不相連。二分圖匹配是指求出一組邊，其中的頂點(diǎn)分別在兩個(gè)集合中，并且任意兩條邊都沒有相同的頂點(diǎn)，這組邊叫做二分圖的匹配，而所能得到的最大的邊的個(gè)數(shù)，叫做最大匹配。 匈牙利算法。這個(gè)算法說白了就是最大流的算法，但是它跟據(jù)二分圖匹配這個(gè)問題的特點(diǎn)，把最大流算法做了簡(jiǎn)化，提高了效率。匈牙利算法其實(shí)很簡(jiǎn)單，但是網(wǎng)上搜不到什么說得清楚的文章。所以我決定要寫一下。
最大流算法的核心問題就是找增廣路徑（augment path）。匈牙利算法也不例外，它的基本模式就是：
初始時(shí)最大匹配為空
while 找得到增廣路徑
do 把增廣路徑加入到最大匹配中去 |
可見和最大流算法是一樣的。但是這里的增廣路徑就有它一定的特殊性，下面我來分析一下。
（注：匈牙利算法雖然根本上是最大流算法，但是它不需要建網(wǎng)絡(luò)模型，所以圖中不再需要源點(diǎn)和匯點(diǎn)，僅僅是一個(gè)二分圖。每條邊也不需要有方向。）
 圖1  圖2
圖1是我給出的二分圖中的一個(gè)匹配：〔1，5〕和〔2，6〕。圖2就是在這個(gè)匹配的基礎(chǔ)上找到的一條增廣路徑：3->6->2->5->1->4。我們借由它來描述一下二分圖中的增廣路徑的性質(zhì)：
(1)有奇數(shù)條邊。
(2)起點(diǎn)在二分圖的左半邊，終點(diǎn)在右半邊。
(3)路徑上的點(diǎn)一定是一個(gè)在左半邊，一個(gè)在右半邊，交替出現(xiàn)。（其實(shí)二分圖的性質(zhì)就決定了這一點(diǎn)，因?yàn)槎謭D同一邊的點(diǎn)之間沒有邊相連，不要忘記哦。）
(4)整條路徑上沒有重復(fù)的點(diǎn)。
(5)起點(diǎn)和終點(diǎn)都是目前還沒有配對(duì)的點(diǎn)，而其它所有點(diǎn)都是已經(jīng)配好對(duì)的。（如圖1、圖2所示，〔1，5〕和〔2，6〕在圖1中是兩對(duì)已經(jīng)配好對(duì)的點(diǎn)；而起點(diǎn)3和終點(diǎn)4目前還沒有與其它點(diǎn)配對(duì)。）
(6)路徑上的所有第奇數(shù)條邊都不在原匹配中，所有第偶數(shù)條邊都出現(xiàn)在原匹配中。（如圖1、圖2所示，原有的匹配是〔1，5〕和〔2，6〕，這兩條配匹的邊在圖2給出的增廣路徑中分邊是第2和第4條邊。而增廣路徑的第1、3、5條邊都沒有出現(xiàn)在圖1給出的匹配中。）
(7)最后，也是最重要的一條，把增廣路徑上的所有第奇數(shù)條邊加入到原匹配中去，并把增廣路徑中的所有第偶數(shù)條邊從原匹配中刪除（這個(gè)操作稱為增廣路徑的取反），則新的匹配數(shù)就比原匹配數(shù)增加了1個(gè)。（如圖2所示，新的匹配就是所有藍(lán)色的邊，而所有紅色的邊則從原匹配中刪除。則新的匹配數(shù)為3。）
不難想通，在最初始時(shí)，還沒有任何匹配時(shí)，圖1中的兩條灰色的邊本身也是增廣路徑。因此在這張二分圖中尋找最大配匹的過程可能如下：
(1)找到增廣路徑1->5，把它取反，則匹配數(shù)增加到1。
(2)找到增廣路徑2->6，把它取反，則匹配數(shù)增加到2。
(3)找到增廣路徑3->6->2->5->1->4，把它取反，則匹配數(shù)增加到3。
(4)再也找不到增廣路徑，結(jié)束。
當(dāng)然，這只是一種可能的流程。也可能有別的找增廣路徑的順序，或者找到不同的增廣路徑，最終的匹配方案也可能不一樣。但是最大匹配數(shù)一定都是相同的。
對(duì)于增廣路徑還可以用一個(gè)遞歸的方法來描述。這個(gè)描述不一定最準(zhǔn)確，但是它揭示了尋找增廣路徑的一般方法：
“從點(diǎn)A出發(fā)的增廣路徑”一定首先連向一個(gè)在原匹配中沒有與點(diǎn)A配對(duì)的點(diǎn)B。如果點(diǎn)B在原匹配中沒有與任何點(diǎn)配對(duì)，則它就是這條增廣路徑的終點(diǎn)；反之，如果點(diǎn)B已與點(diǎn)C配對(duì)，那么這條增廣路徑就是從A到B，再從B到C，再加上“從點(diǎn)C出發(fā)的增廣路徑”。并且，這條從C出發(fā)的增廣路徑中不能與前半部分的增廣路徑有重復(fù)的點(diǎn)。
比如圖2中，我們要尋找一條從3出發(fā)的增廣路徑，要做以下3步：
(1)首先從3出發(fā)，它能連到的點(diǎn)只有6，而6在圖1中已經(jīng)與2配對(duì)，所以目前的增廣路徑就是3->6->2再加上從2出發(fā)的增廣路徑。
(2)從2出發(fā)，它能連到的不與前半部分路徑重復(fù)的點(diǎn)只有5，而且5確實(shí)在原匹配中沒有與2配對(duì)。所以從2連到5。但5在圖1中已經(jīng)與1配對(duì)，所以目前的增廣路徑為3->6->2->5->1再加上從1出發(fā)的增廣路徑。
(3)從1出發(fā)，能連到的不與自已配對(duì)并且不與前半部分路徑重復(fù)的點(diǎn)只有4。因?yàn)?在圖1中沒有與任何點(diǎn)配對(duì)，所以它就是終點(diǎn)。所以最終的增廣路徑是3->6->2->5->1->4。
但是嚴(yán)格地說，以上過程中從2出發(fā)的增廣路徑（2->5->1->4）和從1出發(fā)的增廣路徑（1->4）并不是真正的增廣路徑。因?yàn)樗鼈儾环锨懊嬷v過的增廣路徑的第5條性質(zhì)，它們的起點(diǎn)都是已經(jīng)配過對(duì)的點(diǎn)。我們?cè)谶@里稱它們?yōu)?#8220;增廣路徑”只是為了方便說明整個(gè)搜尋的過程。而這兩條路徑本身只能算是兩個(gè)不為外界所知的子過程的返回結(jié)果。
顯然，從上面的例子可以看出，搜尋增廣路徑的方法就是DFS，可以寫成一個(gè)遞歸函數(shù)。當(dāng)然，用BFS也完全可以實(shí)現(xiàn)。
至此，理論基礎(chǔ)部份講完了。但是要完成匈牙利算法，還需要一個(gè)重要的定理：
如果從一個(gè)點(diǎn)A出發(fā)，沒有找到增廣路徑，那么無論再從別的點(diǎn)出發(fā)找到多少增廣路徑來改變現(xiàn)在的匹配，從A出發(fā)都永遠(yuǎn)找不到增廣路徑。
要用文字來證明這個(gè)定理很繁，話很難說，要么我還得多畫一張圖，我在此就省了。其實(shí)你自己畫幾個(gè)圖，試圖舉兩個(gè)反例，這個(gè)定理不難想通的。（給個(gè)提示。如果你試圖舉個(gè)反例來說明在找到了別的增廣路徑并改變了現(xiàn)有的匹配后，從A出發(fā)就能找到增廣路徑。那么，在這種情況下，肯定在找到別的增廣路徑之前，就能從A出發(fā)找到增廣路徑。這就與假設(shè)矛盾了。）
有了這個(gè)定理，匈牙利算法就成形了。如下：
初始時(shí)最大匹配為空
for 二分圖左半邊的每個(gè)點(diǎn)i
do 從點(diǎn)i出發(fā)尋找增廣路徑。如果找到，則把它取反（即增加了總了匹配數(shù)）。 |
如果二分圖的左半邊一共有n個(gè)點(diǎn)，那么最多找n條增廣路徑。如果圖中共有m條邊，那么每找一條增廣路徑（DFS或BFS）時(shí)最多把所有邊遍歷一遍，所花時(shí)間也就是m。所以總的時(shí)間大概就是O（n * m）。 |
問題:
http://poj.org/problem?id=2005思路:
簡(jiǎn)單題，但是容易錯(cuò)
特殊情況: 兩張牌都是Ace，這也是Ace需要被當(dāng)作是1的唯一情況
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 int player, dealer;
5 int n, count[14];
6 char card[3][2];
7
8 int
9 score(char ch)
10 {
11 if(ch == 'A')
12 return 11;
13 else if(ch == 'T' || ch=='J' || ch=='Q' || ch=='K')
14 return 10;
15 else
16 return ch-'0';
17 }
18
19 int
20 main(int argc, char **argv)
21 {
22 int i, tmp, total;
23 while(scanf("%d", &n)!=EOF && n) {
24 total = player = dealer = 0; memset(count, 0, sizeof(count));
25 for(i=0; i<3; i++) {
26 scanf("%s", card[i]);
27 tmp = score(card[i][0]);
28 ++count[tmp];
29 if(i == 0)
30 dealer += tmp;
31 else
32 player += tmp;
33 }
34 if(player == 22) /* two Ace */
35 player = 12;
36 for(i=2; i<=11; i++) {
37 if((dealer+i==22 ? 12 : dealer+i) < player) {
38 if(i == 10)
39 total += (4*4*n-count[i]);
40 else
41 total += (4*n-count[i]);
42 }
43 }
44 printf("%.3f%%\n\n", ((double)total)/(52*n-3)*100);
45 }
46 }
問題:
http://poj.org/problem?id=3670思路:
1.
將原問題化解為求最長不下降子序列和最長不上升子序列即可
求解LIS/LDS的nlogn算法
參考
http://www.shnenglu.com/Joe/archive/2010/08/14/123461.html2.
參考:
http://www.byvoid.com/blog/usaco-feb08-silver-eating-together/代碼:
1 /* LIS/LDS: nlogn */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_LEN 30001
6 int N, group[MAX_LEN];
7 int aux[MAX_LEN];
8
9 int
10 bin_search1(int *arr, int front, int rear, int target)
11 {
12 int mid;
13 while(front <= rear) {
14 mid = (front+rear)/2;
15 if(aux[mid] <= target)
16 front = mid+1;
17 else
18 rear = mid-1;
19 }
20 return front;
21 }
22
23 int
24 bin_search2(int *arr, int front, int rear, int target)
25 {
26 int mid;
27 while(front <= rear) {
28 mid = (front+rear)/2;
29 if(aux[mid] >= target)
30 front = mid+1;
31 else
32 rear = mid-1;
33 }
34 return front;
35 }
36
37 int
38 LIS() /* LUDS, maybe more accurate, meaning Longest Undecreasing Seq */
39 {
40 int i, len = 1;
41 aux[1] = group[0];
42 for(i=1; i<N; i++) {
43 if(group[i] >= aux[len]) {
44 ++len;
45 aux[len] = group[i];
46 } else {
47 aux[bin_search1(aux, 1, len, group[i])] = group[i];
48 }
49 }
50 return len;
51 }
52
53 int
54 LDS() /* LUIS */
55 {
56 int i, len=1;
57 aux[1] = group[0];
58 for(i=1; i<N; i++) {
59 if(group[i] <= aux[len]) {
60 ++len;
61 aux[len] = group[i];
62 } else {
63 aux[bin_search2(aux, 1, len, group[i])] = group[i];
64 }
65 }
66 return len;
67 }
68
69 int
70 main(int argc, char **argv)
71 {
72 int i, lis_len, lds_len;
73 while(scanf("%d", &N) != EOF) {
74 for(i=0; i<N; i++)
75 scanf("%d", group+i);
76 lis_len = LIS();
77 lds_len = LDS();
78 printf("%d\n", N-(lis_len>lds_len ? lis_len : lds_len));
79 }
80 }
問題:
http://poj.org/problem?id=3090思路:
首先可以觀察得到這樣的點(diǎn)集是對(duì)稱的，只需要求一半即可
這里，我采用了模擬的方法，直接去掉擋住的點(diǎn)
結(jié)果TLE，然后發(fā)現(xiàn)可以打表，隨即AC，打表真是強(qiáng)大啊呵呵...
ps.
據(jù)說這題與什么歐拉函數(shù)有關(guān)系，沒有深究
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 1001
5 int N, points[MAX_LEN][MAX_LEN];
6 int result[MAX_LEN];
7
8 /* Attention: symmetrical */
9 void
10 solve()
11 {
12 int i, j, k, count = 0;
13 memset(points, 0, sizeof(points));
14 for(i=1; i<MAX_LEN; i++) {
15 for(j=0; j<i; j++) {
16 if(!points[i][j])
17 ++count;
18 for(k=1; i*k<MAX_LEN&&j*k<MAX_LEN; k++)
19 points[i*k][j*k] = 1;
20 }
21 result[i] = count;
22 }
23 }
24
25 int
26 main(int argc, char **argv)
27 {
28 int i, tests;
29 solve();
30 scanf("%d", &tests);
31 for(i=1; i<=tests; i++) {
32 scanf("%d", &N);
33 printf("%d %d %d\n", i, N, ((result[N]<<1)+1));
34 }
35 }