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

            堅信:勤能補拙

            PKU 1270 Following Orders

            問題:
            http://acm.pku.edu.cn/JudgeOnline/problem?id=1270

            思路:
            拓撲排序適合于描述事件發(fā)生的先后次序
            這題,對于a>b這樣的題目要求,就非常適合用拓撲排序來進行

            一次AC,寫的過程還接了個女朋友的電話,跟同學聊了會天,o(∩_∩)o...哈哈

            代碼:
             1 #include<stdio.h>
             2 #include<stdlib.h>
             3 #include<string.h>
             4 #define STR_LEN 207
             5 #define MAX_N 26
             6 int adj[MAX_N][MAX_N], in_dgr[MAX_N];
             7 int visited[MAX_N];
             8 int total, ch[MAX_N];
             9 char ans[MAX_N];
            10 
            11 int
            12 init()
            13 {
            14     int i, f, t, len;
            15     char str[STR_LEN];
            16     total = 0;
            17     memset(ch, 0sizeof(ch));
            18     memset(in_dgr, 0sizeof(in_dgr));
            19     memset(adj, 0sizeof(adj));
            20     memset(visited, 0sizeof(visited));
            21     memset(ans, 0sizeof(ans));
            22     if(fgets(str, STR_LEN, stdin) == NULL)
            23         return 0;
            24     len = strlen(str);
            25     for(i=0; i<len; i+=2) {
            26         if(str[i]>='a' && str[i]<='z') {
            27             ++total;
            28             ++ch[str[i]-'a'];
            29         }
            30     }
            31     fgets(str, STR_LEN, stdin);
            32     len = strlen(str);
            33     for(i=0; i<len; i+=2) {
            34         if((i>>1)%2 == 0)
            35             f = str[i]-'a';
            36         else {
            37             t = str[i]-'a';
            38             adj[f][t] = 1;
            39             ++in_dgr[t];
            40         }
            41     }
            42     return 1;
            43 }
            44 
            45 void
            46 topo_sort(int depth)
            47 {
            48     int i, j;
            49     if(depth == total) {
            50         printf("%s\n", ans);
            51         return;
            52     }
            53     for(i=0; i<MAX_N; i++) {
            54         if(ch[i] && !visited[i] && !in_dgr[i]) {
            55             visited[i] = 1;
            56             ans[depth] = 'a'+i;
            57             for(j=0; j<MAX_N; j++)
            58                 if(adj[i][j])
            59                     --in_dgr[j];
            60             topo_sort(depth+1);
            61             visited[i] = 0;
            62             for(j=0; j<MAX_N; j++)
            63                 if(adj[i][j])
            64                     ++in_dgr[j];
            65         }
            66     }
            67 }
            68 
            69 int
            70 main(int argc, char **argv)
            71 {
            72     while(init()) {
            73         topo_sort(0);
            74         printf("\n");
            75     }
            76 }

            posted on 2010-09-14 20:00 simplyzhao 閱讀(186) 評論(0)  編輯 收藏 引用 所屬分類: G_其他

            導航

            <2010年9月>
            2930311234
            567891011
            12131415161718
            19202122232425
            262728293012
            3456789

            統(tǒng)計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            亚洲伊人久久综合影院| 国内精品久久久久影院日本| 久久免费精品一区二区| 亚洲嫩草影院久久精品| 久久精品国产亚洲av瑜伽| 久久免费看黄a级毛片| 久久人人爽爽爽人久久久| 日本久久久久久中文字幕| 久久中文字幕精品| 国产一区二区三区久久精品| 久久精品无码专区免费| 亚洲中文久久精品无码| 国产农村妇女毛片精品久久| 免费无码国产欧美久久18| 国产成人久久精品麻豆一区| 色综合久久久久综合体桃花网 | 欧美伊人久久大香线蕉综合69| 欧美精品国产综合久久| 国产精品热久久无码av| …久久精品99久久香蕉国产| 狠狠色丁香婷婷久久综合五月| 嫩草影院久久99| 亚洲级αV无码毛片久久精品| 久久综合久久伊人| 久久成人精品| 久久国产综合精品五月天| 国内精品久久久久久野外| 久久综合狠狠综合久久综合88 | 国内精品久久久久影院优| 久久这里都是精品| 欧美精品丝袜久久久中文字幕 | 精品久久久久国产免费| 精品999久久久久久中文字幕| 欧美牲交A欧牲交aⅴ久久| 思思久久99热只有频精品66| 久久久久久久综合狠狠综合| 亚洲午夜精品久久久久久app| 久久有码中文字幕| 无码任你躁久久久久久老妇App| 久久久久国产精品三级网| 久久综合久久性久99毛片|