青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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

常用鏈接

留言簿(8)

隨筆檔案

文章檔案

Friends

OJ

搜索

  •  

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            性欧美精品高清| 性色av一区二区三区在线观看| 欧美综合77777色婷婷| 好看的日韩av电影| 欧美黄在线观看| 欧美久久久久| 午夜久久美女| 久久蜜臀精品av| 日韩午夜av| 午夜精品视频在线观看| 红桃视频国产一区| 亚洲精品国产无天堂网2021| 欧美日韩aaaaa| 久久精品首页| 欧美激情按摩在线| 欧美一区二区三区免费在线看| 欧美一乱一性一交一视频| 亚洲第一精品电影| 亚洲天堂av在线免费观看| 国内一区二区在线视频观看| 亚洲大胆人体视频| 国产模特精品视频久久久久| 开心色5月久久精品| 欧美日本免费| 欧美jizz19hd性欧美| 欧美日韩一区国产| 免费在线观看成人av| 欧美色图麻豆| 欧美激情亚洲自拍| 国产一区二区三区日韩| 亚洲精品在线一区二区| 国一区二区在线观看| 日韩天堂在线观看| 亚洲国产精品ⅴa在线观看 | 老司机精品导航| 欧美午夜视频在线观看| 欧美国产日韩免费| 国产综合香蕉五月婷在线| 艳妇臀荡乳欲伦亚洲一区| 亚洲国产欧美在线人成| 欧美一级大片在线免费观看| 一卡二卡3卡四卡高清精品视频| 欧美综合二区| 久久精品1区| 国产精品欧美久久| 亚洲毛片视频| 99视频日韩| 欧美成人亚洲| 欧美激情中文字幕一区二区| 国产一区二区三区四区老人| 亚洲一区二区视频在线| 亚洲网站在线观看| 欧美日韩大片| 亚洲精品自在久久| 99在线精品视频在线观看| 老司机久久99久久精品播放免费| 久久久999精品视频| 国产欧美一区二区精品仙草咪 | 欧美不卡视频| 亚洲国产精品热久久| 久久久午夜电影| 狼人社综合社区| 精品成人国产在线观看男人呻吟| 亚洲欧美三级在线| 欧美在线一区二区三区| 国产精品青草综合久久久久99 | 久久精品99无色码中文字幕| 久久精品一区二区国产| 国产一区激情| 久久久久久久网| 亚洲国产精品一区二区久| 亚洲精品国精品久久99热一| 欧美国产日本韩| 亚洲人成在线影院| 亚洲性av在线| 国产视频久久久久| 久久久精品久久久久| 蜜桃av噜噜一区| 亚洲免费观看高清完整版在线观看熊| 欧美大胆a视频| 日韩午夜免费| 欧美综合国产精品久久丁香| 国产欧美日韩在线视频| 久久免费99精品久久久久久| 欧美国产一区二区在线观看| 99精品视频免费| 国产欧美高清| 美玉足脚交一区二区三区图片| 亚洲国产mv| 欧美一区二区三区视频免费播放| 国产一区二区三区电影在线观看 | 午夜精品久久久久久久久久久| 久久中文字幕一区| 一区二区不卡在线视频 午夜欧美不卡在 | 久久久无码精品亚洲日韩按摩| 1024亚洲| 国产精品久久久久久久久久三级| 欧美高清在线视频观看不卡| 欧美一区二区私人影院日本| 欧美激情精品久久久久久蜜臀| 日韩亚洲欧美中文三级| 久久精品亚洲精品国产欧美kt∨| 亚洲国产一区二区三区a毛片| 欧美日韩成人在线播放| 久久精品99国产精品日本| 亚洲人成在线观看一区二区| 久久av一区二区三区漫画| 亚洲人成网站在线播| 国产美女精品在线| 欧美日韩精品免费| 理论片一区二区在线| 亚洲欧美日韩一区在线| 亚洲精品乱码久久久久久蜜桃麻豆| 久久精品国产亚洲a| 日韩午夜av在线| 亚洲国产精品久久精品怡红院| 国产精品永久免费视频| 欧美久久久久久久久久| 久久综合狠狠综合久久激情| 亚洲宅男天堂在线观看无病毒| 亚洲缚视频在线观看| 久久天堂国产精品| 欧美一区二区性| 亚洲影院免费观看| 一本一本久久a久久精品综合妖精| 尤物九九久久国产精品的分类| 国产视频久久久久久久| 国产精品免费看| 国产精品国产自产拍高清av| 欧美国产先锋| 免费看亚洲片| 麻豆乱码国产一区二区三区| 欧美中文在线视频| 欧美在线看片| 久久不射中文字幕| 久久精品综合| 久久婷婷av| 麻豆久久婷婷| 欧美成人中文字幕| 久久在线免费| 欧美v亚洲v综合ⅴ国产v| 久久一区激情| 欧美mv日韩mv国产网站app| 久久久亚洲国产天美传媒修理工| 欧美在线一二三四区| 久久成人综合视频| 久久精品国产亚洲一区二区三区| 欧美一级大片在线观看| 久久国产精品高清| 麻豆av一区二区三区| 麻豆精品在线播放| 欧美日韩国产美女| 国产精品久久久91| 国产一级揄自揄精品视频| 国产一区二区三区在线播放免费观看 | 亚洲黄色毛片| 一区二区高清视频| 性欧美xxxx大乳国产app| 久久av资源网| 欧美成人自拍| 国产精品女主播| 韩国av一区二区三区在线观看| 在线欧美日韩国产| 国产精品99久久久久久白浆小说| 亚洲一区日韩| 老巨人导航500精品| 亚洲激情网站| 欧美一区二区视频97| 老妇喷水一区二区三区| 欧美日韩第一区日日骚| 国产日韩专区在线| 亚洲精品国精品久久99热一| 亚洲女同同性videoxma| 久热综合在线亚洲精品| 日韩一级在线| 久久久91精品| 欧美日韩伊人| 亚洲国产精品久久久久秋霞蜜臀| 亚洲无吗在线| 欧美成人高清| 亚洲欧美日韩国产一区二区三区| 麻豆久久精品| 国产一区二区无遮挡| 亚洲美女中文字幕| 久久久av网站| 一本色道久久综合亚洲精品小说 | 久久久www成人免费毛片麻豆| 欧美日韩成人网| 怡红院av一区二区三区| 亚洲字幕一区二区| 亚洲福利国产| 久久精品日韩| 国产九九视频一区二区三区| 最新亚洲视频| 另类图片综合电影| 欧美伊人精品成人久久综合97| 欧美亚州在线观看| 日韩午夜黄色| 亚洲第一搞黄网站| 老司机一区二区三区|