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

            ArcTan

            dfs
            隨筆 - 16, 文章 - 117, 評論 - 6, 引用 - 0
            數據加載中……

            SRM549 DIVⅡ 1000pt(AOV網拓撲排序)

            Problem Statement

                 The Order of the Hats is a magical organization. One of their duties is to teach students how to cast spells. There are N spells numbered from 0 to N-1. As an aid for the students, the teachers have prepared a spell chart. The chart lists suggestions on the order in which to study the spells. (This is explained in more detail below.)

            Recently, some changelings broke into the Order's spell archive and messed up the spell chart. You are given a String[] spellChart containing the new, messed-up state of the spell chart. Each character of each element of spellChart is either 'Y' or 'N'. The students will come to study soon. They will interpret the chart in the following way: If spellChart[i][j] is 'Y' then spell i must be learned before spell j.

            As the chart is now messed up, it may be impossible to learn all the spells in the chart because of cycles in the requirements. Your task is to repair the given chart. Determine the minimum number of changes needed to remove all the cycles in the requirements. In a single change, you may either change some character spellChart[i][j] from 'Y' to 'N', or change some character from 'N' to 'Y'.

            Definition

                
            Class: OrderOfTheHats
            Method: minChanged
            Parameters: String[]
            Returns: int
            Method signature: int minChanged(String[] spellChart)
            (be sure your method is public)
                

            Constraints

            - spellChart will contain between 1 and 20 elements, inclusive.
            - Each element of spellChart will contain N characters, where N is the number of elements in spellChart.
            - Each character in each element of spellChart will be either 'Y' or 'N'.

            Examples

            0)
                
            {"Y"}
            Returns: 1
            This spell chart contains a spell that should be learned before itself. The students would never be able to learn such a spell. We can remove this cyclic dependency by changing the 'Y' to 'N'.
            1)
                
            {"NYN",  "NNY",  "NNN"}
            Returns: 0
            This spell chart is already OK.
            2)
                
            {"NYN",  "NNY",  "YNN"}
            Returns: 1
            Changing any single 'Y' to a 'N' will fix this spell chart.
            3)
                
            {"NYYYYYY",  "YNYYYYY",  "YYNYYYY",  "YYYNYYY",  "YYYYNYY",  "YYYYYNY",  "YYYYYYN"}
            Returns: 21

            4)
                
            {"NNNY",  "YNYN",  "YNNN",  "YYYN"}
            Returns: 1

            5)
                
            {"YYYYYNNYYYNYNNNNYNNY",  "NYNNNYYNNYNYYYNYYYYY",  "NNYNNNYYNNNNNNYYYYNY",  "YYNYNYYNNYYYNYNNNYYY",  "NYYNNYNYNYNNNNYYYNYN",  "NNNNNYYNYNNYYYYNYYYN",  "YNYNYYNNNYNNNNNYNNYY",  "NYYYYNYNYNNYNNYNNNNY",  "YYYYNYYNNYYYNNYNNYNY",  "YYYYYYNYNYNYNNNNNNYN",  "NNYYYYYNNNYNNNYNNNNY",  "YYNNNYNYYNYYNYYNYNYN",  "NNYNYYNYYNYYNYNYNYYN",  "YNYNYYNYNNNYNYNYYNYY",  "NNYNNNYYYYYYYYYYYNYY",  "YYYYYNYYNYYYYYNNYNNN",  "NYYYYYYYYNNNNNYYNNYN",  "YNNYNNNYYNYYYNYNYYYY",  "YYNNYNYYYNYYNNNYYNNY",  "NNYNYNYYYNYYNYNNYNNN"}
            Returns: 79

            6)
                
            {"YYNYNN",  "YNYNNY",  "YYYYNN",  "NNNYNN",  "NNNYNN",  "YNYNYN"}
            Returns: 5

            7)
                
            {"NNNNNNNNNN",  "NNNNNNNNNN",  "NNNYNNYNNN",  "NNNYNNYNNN",  "NNNYNNYNNN",  "NNNNNNNNNN",  "NNYYYYYYNN",  "NNYNNNNYNN",  "NNNYYYYNNN",  "NNNNNNNNNN"}
            Returns: 6

            This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.




            題意:給定一張N*N的map,N個頂點的圖,map[i][j]=='Y',<i,j>,否則<j,i>。求最小的轉換Y或者N,使該圖沒有環!

            思路:怎么做呢?thinking




            posted on 2012-07-10 09:59 wangs 閱讀(262) 評論(0)  編輯 收藏 引用 所屬分類: Topcoder

            精品无码人妻久久久久久| 国产毛片欧美毛片久久久| 国产精品久久久久久一区二区三区| 99久久中文字幕| 欧美精品一本久久男人的天堂| 精品蜜臀久久久久99网站| 波多野结衣中文字幕久久| 亚洲一本综合久久| 伊人久久国产免费观看视频| 久久AV高清无码| 无码任你躁久久久久久| 亚洲国产小视频精品久久久三级 | 无码人妻久久一区二区三区免费 | 国产成人精品久久亚洲高清不卡 | 中文字幕久久欲求不满| 久久亚洲av无码精品浪潮| 久久综合给合久久狠狠狠97色69| 精品免费久久久久久久| 奇米综合四色77777久久| 久久国产免费观看精品| 久久丫忘忧草产品| 久久无码专区国产精品发布| www性久久久com| 久久99精品久久久久久hb无码| 久久99中文字幕久久| 99久久99久久精品国产片果冻| 国产成人精品久久亚洲| 国产精品久久久久影视不卡| 色综合久久综合中文综合网| 国产成人精品久久免费动漫| 麻豆久久| 久久久久99精品成人片欧美| 久久国产影院| 精品国产乱码久久久久久郑州公司| 久久本道综合久久伊人| 久久人人爽人人爽人人片AV麻豆| 精品久久久久久国产| 亚洲一本综合久久| 奇米影视7777久久精品| 精品综合久久久久久97超人 | 日韩人妻无码精品久久久不卡|