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

            堅信:勤能補拙

            2011搜索-題,DFS,圖著色

            代碼:
            #include<stdio.h>
            #include
            <stdlib.h>
            #include
            <string.h>
            #include
            <limits.h>
            #define MAX_NUM 26
            char adj[MAX_NUM][MAX_NUM];
            int num, ret, colors[MAX_NUM];

            int
            is_valid(
            int depth, int color)
            {
                
            int i;
                
            for(i=0; i<depth; ++i) {
                    
            if(adj[i][depth] && colors[i]==color)
                        
            return 0;
                }
                
            return 1;
            }

            void
            dfs(
            int depth, int color_used)
            {
                
            if(color_used >= ret)
                    
            return;
                
            if(depth >= num) {
                    ret 
            = color_used;
                    
            return;
                }

                
            int i;
                
            for(i=0; i<color_used; ++i) {
                    
            if(is_valid(depth, i)) {
                        colors[depth] 
            = i;
                        dfs(depth
            +1, color_used);
                        colors[depth] 
            = -1;
                    }
                }    
                colors[depth] 
            = color_used;
                dfs(depth
            +1, color_used+1);
                colors[depth] 
            = -1;
            }

            int
            main(
            int argc, char **argv)
            {
                
            int i;
                
            char info[MAX_NUM+2], *ptr;

                
            while(scanf("%d"&num)!=EOF && num) {
                    ret 
            = INT_MAX;
                    memset(colors, 
            -1sizeof(colors));
                    memset(adj, 
            0sizeof(adj));
                    
            for(i=0; i<num; ++i) {
                        scanf(
            "%s", info);
                        ptr 
            = info+2;
                        
            while(*ptr != '\0') {
                            adj[i][(
            *ptr)-'A'= 1;
                            
            ++ptr;
                        }
                    }
                    dfs(
            00);
                    printf(
            "%d %s needed.\n", ret, ret<=1?"channel":"channels");
                }
            }

            Channel Allocation
            Time Limit: 1000MSMemory Limit: 10000K
            Total Submissions: 8353Accepted: 4248

            Description

            When a radio station is broadcasting over a very large area, repeaters are used to retransmit the signal so that every receiver has a strong signal. However, the channels used by each repeater must be carefully chosen so that nearby repeaters do not interfere with one another. This condition is satisfied if adjacent repeaters use different channels. 

            Since the radio frequency spectrum is a precious resource, the number of channels required by a given network of repeaters should be minimised. You have to write a program that reads in a description of a repeater network and determines the minimum number of channels required.

            Input

            The input consists of a number of maps of repeater networks. Each map begins with a line containing the number of repeaters. This is between 1 and 26, and the repeaters are referred to by consecutive upper-case letters of the alphabet starting with A. For example, ten repeaters would have the names A,B,C,...,I and J. A network with zero repeaters indicates the end of input. 

            Following the number of repeaters is a list of adjacency relationships. Each line has the form: 

            A:BCDH 

            which indicates that the repeaters B, C, D and H are adjacent to the repeater A. The first line describes those adjacent to repeater A, the second those adjacent to B, and so on for all of the repeaters. If a repeater is not adjacent to any other, its line has the form 

            A: 

            The repeaters are listed in alphabetical order. 

            Note that the adjacency is a symmetric relationship; if A is adjacent to B, then B is necessarily adjacent to A. Also, since the repeaters lie in a plane, the graph formed by connecting adjacent repeaters does not have any line segments that cross. 

            Output

            For each map (except the final one with no repeaters), print a line containing the minumum number of channels needed so that no adjacent channels interfere. The sample output shows the format of this line. Take care that channels is in the singular form when only one channel is required.

            Sample Input

            2
            A:
            B:
            4
            A:BC
            B:ACD
            C:ABD
            D:BC
            4
            A:BCD
            B:ACD
            C:ABD
            D:ABC
            0

            Sample Output

            1 channel needed.
            3 channels needed.
            4 channels needed. 

            Source



            posted on 2011-08-14 10:32 simplyzhao 閱讀(283) 評論(0)  編輯 收藏 引用 所屬分類: R_找工復習2011

            導航

            <2011年8月>
            31123456
            78910111213
            14151617181920
            21222324252627
            28293031123
            45678910

            統計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            亚洲欧洲日产国码无码久久99| 国产精品一区二区久久精品无码| 最新久久免费视频| 欧美色综合久久久久久| 亚洲AV无码久久精品色欲| 久久精品国产亚洲沈樵| 久久久精品久久久久久| 午夜人妻久久久久久久久| 久久精品男人影院| 亚洲婷婷国产精品电影人久久| 人妻无码久久一区二区三区免费| 青草影院天堂男人久久| 无码精品久久久久久人妻中字| 久久免费国产精品一区二区| 久久久久亚洲AV成人网人人网站| 久久精品国产秦先生| 狠狠色噜噜色狠狠狠综合久久| 国产激情久久久久影院老熟女免费 | 国产精品99久久免费观看| 久久国产V一级毛多内射| 国内精品久久久久影院日本| 国产精品久久久久久久app| 精品久久人人做人人爽综合| 久久本道伊人久久| 久久国产高潮流白浆免费观看| 欧美精品丝袜久久久中文字幕 | 精品久久综合1区2区3区激情| 国产成人无码久久久精品一| 国内精品综合久久久40p| 亚洲精品无码专区久久同性男| 精品视频久久久久| 久久婷婷色综合一区二区| 久久se精品一区二区影院 | 亚洲精品NV久久久久久久久久| 色综合久久88色综合天天| 精品午夜久久福利大片| 久久精品一区二区国产| 久久精品国产免费| 久久99精品久久久久久秒播| 精品久久人人做人人爽综合| 欧美国产精品久久高清|