青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

A Za, A Za, Fighting...

堅(jiān)信:勤能補(bǔ)拙

問題:
http://poj.org/problem?id=2312

思路:
這題糾結(jié)了...一上午都沒寫出來,原以為很簡單的(其實(shí),很多人都說是簡單題,艾)
首先想到的是廣搜,因?yàn)槭乔髲脑袋c(diǎn)到目的地的最小步數(shù)嘛,典型的BFS,結(jié)果卻始終不知道如何表示每個(gè)狀態(tài)以及狀態(tài)間的判重
既然廣搜不會,那就深搜吧,恩,很快就寫出代碼,結(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[] = {00-11};
11 const int dy[] = {-1100};
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 }


posted @ 2010-10-23 13:33 simplyzhao 閱讀(248) | 評論 (0)編輯 收藏
問題:
http://poj.org/problem?id=3561

思路:
簡單題,結(jié)果卻WA了一次
注意題目中給出的定義: in adjacent cells
就是說,這些符號必須是連續(xù)的,否則就要算兩個(gè)
另一點(diǎn)就是符號'\'需要寫成'\\',開始編譯錯(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, 01, ch);
36                         break;
37                     case '|':
38                         ++vert;
39                         mark(i, j, -10, ch);
40                         mark(i, j, 10, ch);
41                         break;
42                     case '\\':
43                         ++diag;
44                         mark(i, j, 11, 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, -11, 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, 0sizeof(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 }
posted @ 2010-10-22 21:23 simplyzhao 閱讀(212) | 評論 (0)編輯 收藏
問題:
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, 0sizeof(mark));
 98             dfs(request, 0000);
 99             output();
100         }
101     }
102     return 0;
103 }
posted @ 2010-10-22 00:38 simplyzhao 閱讀(322) | 評論 (0)編輯 收藏
問題:
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, 0sizeof(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, -1sizeof(fwd));
62     memset(bwd, -1sizeof(bwd));
63     for(i=0; i<M; i++) {
64         if(fwd[i] == -1) {
65             memset(state, 0sizeof(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 }
posted @ 2010-10-21 00:18 simplyzhao 閱讀(429) | 評論 (0)編輯 收藏

在一個(gè)PXP的有向圖中,路徑覆蓋就是在圖中找一些路經(jīng),使之覆蓋了圖中的所有頂點(diǎn),且任何一個(gè)頂點(diǎn)有且只有一條路徑與之關(guān)聯(lián);(如果把這些路徑中的每條路徑從它的起始點(diǎn)走到它的終點(diǎn),那么恰好可以經(jīng)過圖中的每個(gè)頂點(diǎn)一次且僅一次);如果不考慮圖中存在回路,那么每每條路徑就是一個(gè)弱連通子集.

由上面可以得出:

1.一個(gè)單獨(dú)的頂點(diǎn)是一條路徑;

2.如果存在一路徑p1,p2,......pk,其中p1 為起點(diǎn),pk為終點(diǎn),那么在覆蓋圖中,頂點(diǎn)p1,p2,......pk不再與其它的頂點(diǎn)之間存在有向邊.

最小路徑覆蓋就是找出最小的路徑條數(shù),使之成為P的一個(gè)路徑覆蓋.

路徑覆蓋與二分圖匹配的關(guān)系:

最小路徑覆蓋=|P|-最大匹配數(shù);

其中最大匹配數(shù)的求法是把P中的每個(gè)頂點(diǎn)pi分成兩個(gè)頂點(diǎn)pi'與pi'',如果在p中存在一條pi到pj的邊,那么在二分圖P'中就有一條連接pi'與pj''的無向邊;這里pi' 就是p中pi的出邊,pj''就是p中pj 的一條入邊;

對于公式:最小路徑覆蓋=|P|-最大匹配數(shù);可以這么來理解;

如果匹配數(shù)為零,那么P中不存在有向邊,于是顯然有:

最小路徑覆蓋=|P|-最大匹配數(shù)=|P|-0=|P|;即P的最小路徑覆蓋數(shù)為|P|;

P'中不在于匹配邊時(shí),路徑覆蓋數(shù)為|P|;

如果在P'中增加一條匹配邊pi'-->pj'',那么在圖P的路徑覆蓋中就存在一條由pi連接pj的邊,也就是說pi與pj 在一條路徑上,于是路徑覆蓋數(shù)就可以減少一個(gè);

如此繼續(xù)增加匹配邊,每增加一條,路徑覆蓋數(shù)就減少一條;直到匹配邊不能繼續(xù)增加時(shí),路徑覆蓋數(shù)也不能再減少了,此時(shí)就有了前面的公式;但是這里只 是說話了每條匹配邊對應(yīng)于路徑覆蓋中的一條路徑上的一條連接兩個(gè)點(diǎn)之間的有向邊;下面來說明一個(gè)路徑覆蓋中的每條連接兩個(gè)頂點(diǎn)之間的有向邊對應(yīng)于一條匹配 邊;

與前面類似,對于路徑覆蓋中的每條連接兩個(gè)頂點(diǎn)之間的每條有向邊pi--->pj,我們可以在匹配圖中對應(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)之間邊的一一對應(yīng)關(guān)系,那么也就說明了前面的公式成立!

posted @ 2010-10-21 00:14 simplyzhao 閱讀(215) | 評論 (0)編輯 收藏
問題:
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, -1sizeof(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, 0sizeof(map));
53         memset(result, -1sizeof(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 }
posted @ 2010-10-20 16:20 simplyzhao 閱讀(199) | 評論 (0)編輯 收藏

二分圖指的是這樣一種圖:其所有的頂點(diǎn)分成兩個(gè)集合M和N,其中M或N中任意兩個(gè)在同一集合中的點(diǎn)都不相連。二分圖匹配是指求出一組邊,其中的頂點(diǎn)分別在兩個(gè)集合中,并且任意兩條邊都沒有相同的頂點(diǎn),這組邊叫做二分圖的匹配,而所能得到的最大的邊的個(gè)數(shù),叫做最大匹配。

匈牙利算法。這個(gè)算法說白了就是最大流的算法,但是它跟據(jù)二分圖匹配這個(gè)問題的特點(diǎn),把最大流算法做了簡化,提高了效率。匈牙利算法其實(shí)很簡單,但是網(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)都是目前還沒有配對的點(diǎn),而其它所有點(diǎn)都是已經(jīng)配好對的。(如圖1、圖2所示,〔1,5〕和〔2,6〕在圖1中是兩對已經(jīng)配好對的點(diǎn);而起點(diǎn)3和終點(diǎn)4目前還沒有與其它點(diǎn)配對。)
(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ù)一定都是相同的。

對于增廣路徑還可以用一個(gè)遞歸的方法來描述。這個(gè)描述不一定最準(zhǔn)確,但是它揭示了尋找增廣路徑的一般方法:
“從點(diǎn)A出發(fā)的增廣路徑”一定首先連向一個(gè)在原匹配中沒有與點(diǎn)A配對的點(diǎn)B。如果點(diǎn)B在原匹配中沒有與任何點(diǎn)配對,則它就是這條增廣路徑的終點(diǎn);反之,如果點(diǎn)B已與點(diǎn)C配對,那么這條增廣路徑就是從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配對,所以目前的增廣路徑就是3->6->2再加上從2出發(fā)的增廣路徑。
(2)從2出發(fā),它能連到的不與前半部分路徑重復(fù)的點(diǎn)只有5,而且5確實(shí)在原匹配中沒有與2配對。所以從2連到5。但5在圖1中已經(jīng)與1配對,所以目前的增廣路徑為3->6->2->5->1再加上從1出發(fā)的增廣路徑。
(3)從1出發(fā),能連到的不與自已配對并且不與前半部分路徑重復(fù)的點(diǎn)只有4。因?yàn)?在圖1中沒有與任何點(diǎn)配對,所以它就是終點(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)配過對的點(diǎn)。我們在這里稱它們?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)。

posted @ 2010-10-20 15:13 simplyzhao 閱讀(215) | 評論 (0)編輯 收藏
問題:
http://poj.org/problem?id=2005

思路:
簡單題,但是容易錯(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, 0sizeof(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 }
posted @ 2010-10-19 21:30 simplyzhao 閱讀(209) | 評論 (0)編輯 收藏
問題:
http://poj.org/problem?id=3670

思路:
1. 
將原問題化解為求最長不下降子序列和最長不上升子序列即可
求解LIS/LDS的nlogn算法
參考http://www.shnenglu.com/Joe/archive/2010/08/14/123461.html

2.
參考: 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 }
posted @ 2010-10-19 14:30 simplyzhao 閱讀(223) | 評論 (0)編輯 收藏
問題:
http://poj.org/problem?id=3090

思路:
首先可以觀察得到這樣的點(diǎn)集是對稱的,只需要求一半即可
這里,我采用了模擬的方法,直接去掉擋住的點(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, 0sizeof(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 }
posted @ 2010-10-18 20:18 simplyzhao 閱讀(183) | 評論 (0)編輯 收藏
僅列出標(biāo)題
共21頁: First 5 6 7 8 9 10 11 12 13 Last 

導(dǎo)航

<2025年9月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

統(tǒng)計(jì)

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            欧美一区二区免费观在线| 国产精品久久夜| 国产一区在线看| 欧美在线不卡| 久久久www| 亚洲品质自拍| 亚洲精品日韩欧美| 国产精品毛片| 久久综合精品一区| 欧美成人一区二区| 中文在线资源观看网站视频免费不卡| 欧美激情一区二区三区四区| 欧美成人国产| 欧美亚洲在线| 蜜桃av一区二区三区| 一本色道久久综合亚洲精品按摩| 亚洲精品国产精品乱码不99 | 亚洲精美视频| 欧美性猛交99久久久久99按摩| 午夜精品短视频| 久久爱www.| 这里是久久伊人| 欧美综合77777色婷婷| 99av国产精品欲麻豆| 亚洲欧美日韩精品久久奇米色影视| 国产综合一区二区| 日韩午夜电影av| 精品999在线播放| 亚洲靠逼com| 亚洲第一中文字幕在线观看| 日韩视频一区二区三区在线播放 | 欧美在线黄色| 亚洲一区免费看| 久久亚裔精品欧美| 欧美一区2区视频在线观看| 欧美成人亚洲成人| 免费人成精品欧美精品| 欧美激情一区二区三区在线视频| 欧美日本一区| 免费成人av| 国产亚洲精久久久久久| 亚洲免费观看高清完整版在线观看熊| 国产精品永久免费| 一本色道久久综合亚洲精品不| 在线免费精品视频| 欧美一区二区视频网站| 亚洲综合社区| 欧美日韩岛国| 欧美激情精品久久久久久大尺度 | 午夜视频在线观看一区二区| 美脚丝袜一区二区三区在线观看 | 久久亚洲国产精品一区二区| 性做久久久久久| 国产精品成人免费精品自在线观看| 亚洲缚视频在线观看| 亚洲第一综合天堂另类专| 西西人体一区二区| 欧美专区在线播放| 国产日韩一区二区| 欧美亚洲尤物久久| 久久精品夜夜夜夜久久| 国产精品一区久久久久| 亚洲一区久久久| 亚洲欧美综合网| 国产伦精品免费视频| 亚洲一区二区三区四区中文 | 亚洲日韩中文字幕在线播放| 亚洲精品免费电影| 欧美好吊妞视频| 亚洲精品美女在线观看| 亚洲精品少妇| 欧美日韩国产影院| 在线午夜精品| 久久精品国产成人| 尤物yw午夜国产精品视频明星| 久久久av网站| 亚洲人成网在线播放| 亚洲视频在线观看| 国产精品一区二区欧美| 欧美在线观看www| 欧美激情导航| 亚洲视频导航| 国产综合网站| 欧美黄色网络| 亚洲中字在线| 欧美大片免费观看在线观看网站推荐| 亚洲黄色成人网| 欧美日韩一区高清| 欧美一区二区女人| 欧美激情按摩在线| 午夜精品久久久久久99热| 国产在线视频欧美一区二区三区| 久久久精品性| 一本大道久久a久久综合婷婷| 免费久久99精品国产自在现线| 亚洲七七久久综合桃花剧情介绍| 中文欧美在线视频| 激情综合久久| 欧美午夜精品久久久久久孕妇 | 久久国产主播精品| 亚洲激情一区二区| 久久黄色影院| 999亚洲国产精| 国语精品中文字幕| 欧美日韩亚洲国产精品| 久久爱www久久做| 一区二区三区欧美| 亚洲高清色综合| 久久国内精品视频| 亚洲一线二线三线久久久| 永久久久久久| 国产伦精品一区二区三区视频孕妇| 久久香蕉国产线看观看av| 亚洲欧美日韩久久精品| 91久久精品www人人做人人爽 | 亚洲黄色天堂| 国产一区二区三区黄视频| 欧美日韩免费一区二区三区| 久久久在线视频| 性欧美8khd高清极品| 夜夜精品视频| 亚洲精品久久久蜜桃| 免费看的黄色欧美网站| 久久精品免费| 性色一区二区三区| 亚洲一区免费看| 亚洲小说区图片区| 99re6这里只有精品| 亚洲国产小视频在线观看| 黑人极品videos精品欧美裸| 国产精品人人做人人爽人人添| 欧美日韩一区自拍| 欧美日韩国产精品一区二区亚洲| 老司机精品视频网站| 久久精品国产久精国产爱| 欧美一区二区精品久久911| 亚洲在线一区二区三区| 一区二区三区黄色| 亚洲人成网站在线播| 亚洲国产免费| 亚洲国产成人久久| 亚洲激情一区二区三区| 亚洲精美视频| 9久re热视频在线精品| 99国产精品久久久久久久| 亚洲精品影院在线观看| 99国产精品久久久| 亚洲一区精品在线| 欧美一区二区播放| 另类成人小视频在线| 免费欧美视频| 欧美日韩国产免费| 国产精品福利在线观看| 国产精品一区二区在线观看不卡| 国产精品视频免费一区| 国产一区久久| 亚洲国产专区校园欧美| 亚洲久久一区| 午夜精品久久久久久久久久久久久 | 久久久久久日产精品| 久久在线观看视频| 亚洲国产日韩精品| 国产精品99久久久久久www| 亚洲深夜激情| 久久九九99视频| 欧美精品系列| 国产农村妇女精品一二区| 一区二区在线观看av| 99成人在线| 久久精品国产一区二区三区| 欧美aⅴ99久久黑人专区| 最新日韩av| 欧美一区二区三区免费视| 久久综合一区| 国产精品久久久久久影视| 狠狠色香婷婷久久亚洲精品| 亚洲欧洲一区二区在线观看| 亚洲一区二区在线视频| 久热这里只精品99re8久| 亚洲精品视频免费| 欧美怡红院视频| 欧美日韩大陆在线| 黄色另类av| 午夜精品久久久久久久男人的天堂 | 狼人社综合社区| 亚洲最黄网站| 麻豆国产va免费精品高清在线| 欧美午夜免费| 99re6热在线精品视频播放速度| 久久高清国产| 一区二区三区日韩精品| 久久综合色8888| 国产日韩一区二区三区在线播放| 亚洲蜜桃精久久久久久久| 久久久精品国产免费观看同学| 亚洲欧洲久久| 免费不卡亚洲欧美| 韩国一区电影| 久久av老司机精品网站导航| 亚洲精品美女久久7777777|