• <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>

            A Za, A Za, Fighting...

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

            問題:
            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[] = {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 閱讀(233) | 評(píng)論 (0)編輯 收藏
            問題:
            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, 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 閱讀(204) | 評(píng)論 (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 閱讀(311) | 評(píng)論 (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 閱讀(420) | 評(píng)論 (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 的一條入邊;

            對(duì)于公式:最小路徑覆蓋=|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í)就有了前面的公式;但是這里只 是說話了每條匹配邊對(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)系,那么也就說明了前面的公式成立!

            posted @ 2010-10-21 00:14 simplyzhao 閱讀(205) | 評(píng)論 (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 閱讀(189) | 評(píng)論 (0)編輯 收藏

            二分圖指的是這樣一種圖:其所有的頂點(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)。

            posted @ 2010-10-20 15:13 simplyzhao 閱讀(204) | 評(píng)論 (0)編輯 收藏
            問題:
            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, 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 閱讀(199) | 評(píng)論 (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 閱讀(209) | 評(píng)論 (0)編輯 收藏
            問題:
            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, 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 閱讀(172) | 評(píng)論 (0)編輯 收藏
            僅列出標(biāo)題
            共21頁: First 5 6 7 8 9 10 11 12 13 Last 

            導(dǎo)航

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            統(tǒng)計(jì)

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            亚洲欧洲精品成人久久奇米网| 亚洲成av人片不卡无码久久| 精品无码久久久久国产动漫3d| 亚洲色大成网站www久久九| 性欧美丰满熟妇XXXX性久久久| 国产国产成人精品久久| 久久久久无码中| 精品久久久久久久久午夜福利| 精品无码久久久久久久久久| 亚洲午夜久久久久久噜噜噜| 精品久久久久久无码人妻蜜桃| 久久AV无码精品人妻糸列| 国产99久久精品一区二区| 怡红院日本一道日本久久| 中文成人无码精品久久久不卡 | 久久精品人人做人人爽97| avtt天堂网久久精品| 午夜精品久久久内射近拍高清| 丰满少妇人妻久久久久久| 狠狠色丁香婷婷久久综合| 热久久这里只有精品| 久久精品国产亚洲AV无码麻豆| 无码任你躁久久久久久| 色综合久久综精品| 99久久99久久| 97热久久免费频精品99| 蜜臀av性久久久久蜜臀aⅴ| 国内精品九九久久精品| 一本大道久久香蕉成人网| 久久久久亚洲爆乳少妇无 | 国内精品久久久久久99蜜桃| 人妻无码精品久久亚瑟影视| 欧美一级久久久久久久大| 精品久久久久久无码国产| 很黄很污的网站久久mimi色| 久久婷婷综合中文字幕| 久久精品欧美日韩精品| 久久精品人人做人人妻人人玩 | 伊人久久亚洲综合影院| 久久综合久久性久99毛片| 怡红院日本一道日本久久 |