• <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 - 7,comments - 3,trackbacks - 0

             1871: Jogging Trails


            ResultTIME LimitMEMORY LimitRun TimesAC TimesJUDGE
            3s8192K5917Standard
            Gord is training for a marathon. Behind his house is a park with a large network of jogging trails connecting water stations. Gord wants to find the shortest jogging route that travels along every trail at least once.

            Input consists of several test cases. The first line of input for each case contains two positive integers: n <= 15, the number of water stations, and m < 1000, the number of trails. For each trail, there is one subsequent line of input containing three positive integers: the first two, between 1 and n, indicating the water stations at the end points of the trail; the third indicates the length of the trail, in cubits. There may be more than one trail between any two stations; each different trail is given only once in the input; each trail can be travelled in either direction. It is possible to reach any trail from any other trail by visiting a sequence of water stations connected by trails. Gord's route may start at any water station, and must end at the same station. A single line containing 0 follows the last test case.

            For each case, there should be one line of output giving the length of Gord's jogging route.

            Sample Input

            4 5
            1 2 3
            2 3 4
            3 4 5
            1 4 10
            1 3 12
            0
            

            Output for Sample Input

            41
            





            古老的圖論問題:中國郵遞員問題,曾經在某個圖論書上看過,之后就沒有之后了......
            題目大意很簡單:給一無向網絡N,從點1出發,每條邊至少進過一次后回到點1。
            思路:(copy別人的)
            1. 先解釋下"度"的概念, 對于無向圖中某結點, 它和n條邊相連, 就稱它的度為n. (有向圖還分出度入度, 這里簡化了, 不管)

            2. 參考歐拉回路的概念, 無向圖存在歐拉回路, 當前僅當所有點度數均為偶數. 
            證明比較簡單, 因為走完一條回路, 對于所有點均進去一次, 出來一次. 故, 對于任意點的度數,都是成對的在"消耗".

            3. 題中所描述的回路, 有重復經過某邊, 這沒關系. 現在假設郵遞員按題目要求走了一條最短的回路P.
            那么, 把P所有重復經過的邊, 拆開. 即假設三次經過邊L, 則我們可以人為的在原圖上多加兩條邊, 對于所有重復經過的邊都這樣做. 修改后的圖記為G2. (原圖為G)
            對于G2, 郵遞員走的回路, 即為此圖的歐拉回路. 這是重點. (其實很好想, 因為G2中的每條邊都僅被郵遞員走過一次.)

            4. 原問題就可以轉化為, 如何把G添加一些邊, 變成G2
            而G2所有點度數均為偶數(這是肯定的, 因為G2存在歐拉回路)
            故轉化為, 如何把G中某些邊復制x次, 從而消滅G中的奇點(度數為奇數的點).

            5. 可能有點暈, 舉個例子
            圖G只有兩個點a和b, 一條邊連著ab, 那么ab均為奇點, 要消滅掉, 就把ab之間連線復制一次(因為你不可能隨便給它加一條不存在的..)
            然后變成兩條邊連著ab. 從G2的角度看, 是歐拉圖了, 對應成G, 就是把這條邊走了兩次而已.

            6. 奇點總是成對的被消滅, 就算兩個奇點不互通, 而是經過很多點才能連通, 那也要連出一條路徑來, 以消滅這對奇點.

            7. 那就好辦了.把所有奇點找出來, 然后配對, 如果某種配對方式代價最小, 即為所求.
            這里還要用上floyd, 求最短路

            8. 配對算法也要比較好, 裸著配大概會超時, 這個懶得說了.. 如果不會, 直接看代碼吧.

            給點扼要注釋, deg記錄度數, mp記錄最短路. u記錄遞歸時各點是否已配對. (偶點直接被記為已配對. 遞歸時只路過)
            dfs返回在當前此種u記錄的配對情況下, 把未配對的匹配完, 最小代價是多少

            還是提一句吧, 每次配對時, 配對中的第一個可以直接取隊列中的第一個沒有配對的元素(其實隨便取都行). 第二個, 循環一次剩下的即可.
            因為配對是不關心順序的, 所以第一個可以想怎么取都行. 為了方便, 就第一個了.

            代碼:
            #include <cstdio>
            #include 
            <cstring>
            #include 
            <cmath>
            #include 
            <iostream>
            #define N 17
            #define inf 1 << 20
            using namespace std;

            int deg[N], map[N][N], u[N];
            int ans, n, m;

            int min(int a, int b)
            {
                
            if (a > b) return b;
                
            return a;
            }

            int slove()
            {
                
            int i, j, rnt = inf;
                
            for (i = 0; i < n; ++i)
                
            if (!u[i]) break;
                
            if (i == n) return 0;
                u[i] 
            = 1;
                
            for (j = i + 1; j < n; ++j)
                {
                    
            if (!u[j]) u[j] = 1, rnt = min(rnt, slove() + map[i][j]), u[j] = 0;
                }
                u[i] 
            = 0;
                
            return rnt;
            }

            int main()
            {
                
            while (scanf("%d"&n) && n)
                {
                    memset(u, 
            0sizeof(u));
                    memset(deg, 
            0sizeof(deg));
                    
            for (int i = 0; i < n; ++i)
                        
            for (int j = 0; j < n; ++j)
                        map[i][j] 
            = inf;
                    ans 
            = 0;
                    scanf(
            "%d"&m);
                    
            for (int i = 1; i <= m; ++i)
                    {
                        
            int a, b, c;
                        scanf(
            "%d%d%d"&a, &b, &c);
                        ans 
            += c;
                        a
            --; b--;
                        deg[a]
            ++;
                        deg[b]
            ++;
                        map[a][b] 
            = map[b][a] = min(map[a][b], c);
                    }
                    
            for (int k = 0; k < n; ++k)
                        
            for (int i = 0; i < n; ++i)
                            
            for (int j = 0; j < n; ++j)
                            {
                                map[i][j] 
            = min(map[i][j], map[i][k] + map[k][j]);
                            }
                    
            for (int i = 0; i < n; ++i)
                    
            if (deg[i] % 2 == 0) u[i] = 1;
                    printf(
            "%d\n", ans + slove());
                }
                
            return 0;
            }
            posted on 2011-10-15 22:13 LLawliet 閱讀(257) 評論(0)  編輯 收藏 引用 所屬分類: 圖論
            日韩AV无码久久一区二区| 久久最新免费视频| 国产成人精品久久| 久久综合久久性久99毛片| 精品人妻伦九区久久AAA片69| 久久精品国产精品亚洲人人| 人人狠狠综合88综合久久| 久久免费国产精品| 久久综合狠狠综合久久综合88| 日本人妻丰满熟妇久久久久久| 中文字幕久久欲求不满| 久久精品国产色蜜蜜麻豆| 99久久香蕉国产线看观香| 精品综合久久久久久97超人| 久久精品极品盛宴观看| 久久综合久久久| 亚洲αv久久久噜噜噜噜噜| 国产精品亚洲综合专区片高清久久久 | 久久人人爽人人爽人人片AV麻烦 | 91久久成人免费| 久久午夜福利无码1000合集| 国产亚洲欧美成人久久片| 久久久久久久精品成人热色戒| 久久国产精品-久久精品| 中文字幕久久精品| 99久久综合狠狠综合久久| 伊人久久大香线蕉av一区| 久久青青草原精品国产不卡| AAA级久久久精品无码片| 久久亚洲日韩看片无码| 欧美午夜A∨大片久久| 99久久精品国产一区二区蜜芽| avtt天堂网久久精品| 亚洲国产精品18久久久久久| 精品伊人久久久| 亚洲国产视频久久| 亚洲国产成人久久一区久久 | 久久只有这里有精品4| 久久久久久av无码免费看大片| 精品国产乱码久久久久久1区2区| 无码人妻久久久一区二区三区 |