• <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>
            posts - 74,  comments - 33,  trackbacks - 0
            Islands and Bridges
            Time Limit: 4000MS Memory Limit: 65536K
            Total Submissions: 2930 Accepted: 723

            Description

            Given a map of islands and bridges that connect these islands, a Hamilton path, as we all know, is a path along the bridges such that it visits each island exactly once. On our map, there is also a positive integer value associated with each island. We call a Hamilton path the best triangular Hamilton path if it maximizes the value described below.

            Suppose there are n islands. The value of a Hamilton path C1C2...Cn is calculated as the sum of three parts. Let Vi be the value for the island Ci. As the first part, we sum over all the Vi values for each island in the path. For the second part, for each edge CiCi+1 in the path, we add the product Vi*Vi+1. And for the third part, whenever three consecutive islands CiCi+1Ci+2 in the path forms a triangle in the map, i.e. there is a bridge between Ci and Ci+2, we add the product Vi*Vi+1*Vi+2.

            Most likely but not necessarily, the best triangular Hamilton path you are going to find contains many triangles. It is quite possible that there might be more than one best triangular Hamilton paths; your second task is to find the number of such paths.

            Input

            The input file starts with a number q (q<=20) on the first line, which is the number of test cases. Each test case starts with a line with two integers n and m, which are the number of islands and the number of bridges in the map, respectively. The next line contains n positive integers, the i-th number being the Vi value of island i. Each value is no more than 100. The following m lines are in the form x y, which indicates there is a (two way) bridge between island x and island y. Islands are numbered from 1 to n. You may assume there will be no more than 13 islands.

            Output

            For each test case, output a line with two numbers, separated by a space. The first number is the maximum value of a best triangular Hamilton path; the second number should be the number of different best triangular Hamilton paths. If the test case does not contain a Hamilton path, the output must be `0 0'.

            Note: A path may be written down in the reversed order. We still think it is the same path.

            Sample Input

            2
            3 3
            2 2 2
            1 2
            2 3
            3 1
            4 6
            1 2 3 4
            1 2
            1 3
            1 4
            2 3
            2 4
            3 4
            

            Sample Output

            22 3
            69 1
            以前做本校的1005的時候,其中就用到TSP,當然KM也能正確求解,暴搜更是無敵!
            現在這是一道變形的TSP,搞清題目意思就很容易求解,不幸的是在統計路徑的時候,我居然
            腦殘的sum++,而應該是sum+=dpways[(1<<n)-1][i][j];因此白白的貢獻了N個WA,
            腦殘人士!請見諒!
            代碼很慢,735ms,不貼了!
            -------------------------------------------------------------------------------------------
            上課去了!!!
            posted on 2009-03-26 09:56 KNIGHT 閱讀(124) 評論(0)  編輯 收藏 引用
            <2009年3月>
            22232425262728
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            人妻系列无码专区久久五月天| 亚洲综合熟女久久久30p| 国产精品久久亚洲不卡动漫| 欧美亚洲色综久久精品国产 | 国产∨亚洲V天堂无码久久久| 久久人人爽人人爽人人AV| 秋霞久久国产精品电影院| 久久99精品国产99久久6| 久久国产精品国语对白| 三级三级久久三级久久| av国内精品久久久久影院| 久久精品国产欧美日韩| 国产成人精品三上悠亚久久| 精品久久久久久国产| 狠狠综合久久AV一区二区三区| 久久99国产精品99久久| 久久久久久久久66精品片| 亚洲综合精品香蕉久久网97| 亚洲国产精品无码久久久久久曰| 久久精品天天中文字幕人妻| 久久中文字幕无码专区| 大伊人青草狠狠久久| 偷窥少妇久久久久久久久| 久久99毛片免费观看不卡 | 国产91色综合久久免费| 日本久久久久久久久久| 97精品国产97久久久久久免费| 国产亚洲精品久久久久秋霞| 久久久久久久综合综合狠狠| 国内精品久久人妻互换| 99久久精品免费看国产一区二区三区 | 日产精品久久久久久久| 久久亚洲国产成人影院| 久久国产高清一区二区三区| 久久成人永久免费播放| 亚洲一本综合久久| 国产精品美女久久久久AV福利| 久久国产精品一区二区| 亚洲国产精品久久66| 狠狠色婷婷综合天天久久丁香 | 久久人人爽人人爽人人爽 |