• <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| 伊人热热久久原色播放www| 开心久久婷婷综合中文字幕| 99久久国产综合精品女同图片| 72种姿势欧美久久久久大黄蕉| 久久精品成人免费国产片小草| 人妻无码αv中文字幕久久琪琪布 人妻无码精品久久亚瑟影视 | 一本大道久久a久久精品综合| 日日狠狠久久偷偷色综合0| 久久亚洲私人国产精品vA| 久久久久亚洲精品无码网址| 日本人妻丰满熟妇久久久久久| 国产无套内射久久久国产| 精品乱码久久久久久久| 一本久久a久久精品综合香蕉 | 日日狠狠久久偷偷色综合免费| 无码人妻精品一区二区三区久久 | 久久笫一福利免费导航| 欧美亚洲另类久久综合| 久久精品国产清自在天天线| 久久精品亚洲男人的天堂| 99久久久精品免费观看国产| 久久人妻无码中文字幕| 欧美日韩精品久久久久| 国产成人精品久久一区二区三区av| 久久精品午夜一区二区福利| 久久99九九国产免费看小说| 久久久精品视频免费观看| 国产福利电影一区二区三区久久久久成人精品综合 | 亚洲综合久久夜AV | 久久久久国产日韩精品网站| 国产精品欧美久久久久天天影视| 69国产成人综合久久精品| 久久天堂AV综合合色蜜桃网| 亚洲中文字幕无码久久2017 | 久久精品无码一区二区三区免费| 青青国产成人久久91网| 国产亚洲色婷婷久久99精品91| 久久99精品国产99久久6| 久久99亚洲综合精品首页|