• <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水蜜桃| 久久影院综合精品| 久久精品无码一区二区日韩AV| 久久精品视频免费| 人妻丰满?V无码久久不卡| 狠狠精品久久久无码中文字幕| 国产精品一久久香蕉国产线看观看| 97久久超碰国产精品2021| 欧美亚洲日本久久精品| 无码AV中文字幕久久专区| 久久精品国产WWW456C0M| 精品久久人人爽天天玩人人妻| 国内精品久久久久| 亚洲乱码中文字幕久久孕妇黑人| 亚洲一本综合久久| 男女久久久国产一区二区三区| 久久久久亚洲AV无码专区网站| 久久亚洲国产成人精品性色| 伊人久久精品影院| 国产一区二区精品久久凹凸 | 波多野结衣久久一区二区| 99久久精品国内| 色婷婷综合久久久久中文| 亚洲精品WWW久久久久久| 久久精品国产精品亜洲毛片 | 久久久久人妻一区二区三区| 久久综合九色综合久99 | 99精品久久久久久久婷婷| 性做久久久久久久久| 精品无码久久久久久久久久| 精品午夜久久福利大片| 国产精品久久国产精品99盘| 99久久精品国产高清一区二区 | 亚洲精品无码久久久久| 性高湖久久久久久久久AAAAA| 国产亚洲精午夜久久久久久| 伊人久久精品线影院| 国产精品青草久久久久福利99| 精品999久久久久久中文字幕| .精品久久久麻豆国产精品| 国产精品久久自在自线观看|