• <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 1129 Channel Allocation

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

            思路:
            好題,典型的圖著色問題
            首先,對于鄰接關系,可以用二維數組來表示
            具有鄰接關系的節點不能使用同一種顏色,求所需顏色的最小值
            深度優先搜索,當目前使用顏色個數已經超過當前最優解時進行減枝

            代碼:
             1 #define MAX_NUM 29
             2 #define INF 100000
             3 int graph[MAX_NUM][MAX_NUM];
             4 int color[MAX_NUM];
             5 int num, ans;
             6 
             7 void
             8 init()
             9 {
            10     int i, j, len;
            11     char conn[MAX_NUM];
            12     memset(graph, 0sizeof(graph));
            13     memset(color, -1sizeof(color));
            14     ans = INF;
            15     for(i=0; i<num; i++) {
            16         scanf("%s", conn);
            17         len = strlen(conn);
            18         for(j=2; j<len; j++)
            19             graph[i][conn[j]-'A'= 1;
            20     }
            21 }
            22 
            23 int
            24 is_valid(int depth, int cindex)
            25 {
            26     int i;
            27     for(i=0; i<depth; i++)
            28         if(graph[depth][i] && color[i]==cindex)
            29             return 0;
            30     return 1;
            31 }
            32 
            33 void 
            34 dfs(int depth, int used_colors)
            35 {
            36     int i;
            37     if(used_colors >= ans) /* pruning */
            38         return;
            39     if(depth == num) {
            40         ans = used_colors<ans ? used_colors : ans;
            41         return;
            42     }
            43     for(i=1; i<=used_colors; i++) {
            44         if(is_valid(depth, i)) {
            45             color[depth] = i;
            46             dfs(depth+1, used_colors);
            47             color[depth] = -1;
            48         }
            49     }
            50     color[depth] = used_colors+1;
            51     dfs(depth+1, used_colors+1);
            52     color[depth] = -1;
            53 }


            posted on 2010-07-26 20:47 simplyzhao 閱讀(215) 評論(0)  編輯 收藏 引用 所屬分類: B_搜索

            導航

            <2010年7月>
            27282930123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567

            統計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久香蕉国产线看观看99| 亚洲国产精品一区二区三区久久 | 狠狠色丁香婷婷综合久久来来去| 久久久九九有精品国产| 国产成人精品久久亚洲| 久久精品中文字幕大胸| 久久精品亚洲一区二区三区浴池| 久久99精品免费一区二区| 精品久久久久久无码不卡| 久久久av波多野一区二区| 国产综合精品久久亚洲| 人妻少妇久久中文字幕一区二区| 国产福利电影一区二区三区久久老子无码午夜伦不| 国产精品久久久久久久午夜片| 亚洲国产精品无码久久久秋霞2 | 中文精品99久久国产 | 精品久久8x国产免费观看| 久久精品无码一区二区三区日韩| 久久综合九色综合网站| 精品久久久久久无码中文野结衣| 久久综合给合久久狠狠狠97色| 亚洲人成无码www久久久| 久久久精品一区二区三区| 久久这里只有精品18| 伊人久久大香线蕉AV色婷婷色| 久久久久综合国产欧美一区二区| 精品国产91久久久久久久| 久久久久亚洲av无码专区喷水 | 99久久99久久精品国产片果冻| 久久久国产精华液| 51久久夜色精品国产| 国产精品久久一区二区三区| 性欧美大战久久久久久久久| 久久久午夜精品福利内容| 久久免费视频6| 免费精品国产日韩热久久| 精品久久人人爽天天玩人人妻| 成人精品一区二区久久久| 国产成人精品久久亚洲高清不卡| 国产精品成人99久久久久91gav| 久久播电影网|