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

            pku 1237 The Postal Worker Rings Once 中國郵路問題簡化版。紀念POJ第500題

            題意:
            Given a sequence of streets (connecting given intersections) you are to write a program that determines the minimal cost tour that traverses every street at least once. The tour must begin and end at the same intersection. 
            給力條件:
            There will be at most two intersections with odd degree
            解法:
            分情況討論:
            1、所有節(jié)點的度都為偶數(shù),那么答案就是所有邊權和
            2、存在兩個奇數(shù)度節(jié)點,那么答案是邊權和加上這兩個奇數(shù)度節(jié)點間的最短距離

            發(fā)現(xiàn)現(xiàn)在越來越依賴STL了,有點小悲劇。。。

            代碼:
             1 # include <cstdio>
             2 # include <vector>
             3 # include <utility>
             4 # include <functional>
             5 # include <cstring>
             6 using namespace std;
             7 vector<pair<int,int> >g[26];
             8 int main()
             9 {
            10     char str[1024];
            11     while(scanf("%s",str)!=EOF)
            12     {
            13        int total=0;
            14        for(int i=0;i<26;i++) g[i].clear();
            15        while(true)
            16        {
            17           if(!strcmp(str,"deadend")) break;
            18           g[str[0]-'a'].push_back(make_pair<int,int>(str[strlen(str)-1]-'a',strlen(str)));
            19           g[str[strlen(str)-1]-'a'].push_back(make_pair<int,int>(str[0]-'a',strlen(str)));
            20           total+=strlen(str);
            21           scanf("%s",str);
            22        }
            23        vector<int> flag;
            24        for(int i=0;i<26;i++)
            25        {
            26           if(g[i].size()%2==1)
            27             flag.push_back(i);
            28        }
            29        if(flag.empty()) printf("%d\n",total);
            30        else
            31        {
            32            int len[26];
            33            bool used[26];
            34            memset(len,-1,sizeof(len));
            35            memset(used,false,sizeof(used));
            36            len[flag[0]]=0;
            37            while(true)
            38            {
            39              int pos=-1,minnum=0xfffffff;
            40              for(int i=0;i<26;i++)
            41                if(!used[i]&&len[i]!=-1&&len[i]<minnum)
            42                  minnum=len[i],pos=i;
            43              if(pos==-1break;
            44              used[pos]=true;
            45              for(int i=0;i<g[pos].size();i++)
            46                if(!used[g[pos][i].first]&&(len[g[pos][i].first]==-1||len[g[pos][i].first]>len[pos]+g[pos][i].second))
            47                   len[g[pos][i].first]=len[pos]+g[pos][i].second;
            48            }
            49            printf("%d\n",total+len[flag[1]]);
            50        } 
            51     }
            52     return  0;
            53 }
            54 

            posted on 2011-01-26 11:59 yzhw 閱讀(350) 評論(0)  編輯 收藏 引用 所屬分類: graph

            <2011年1月>
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            導航

            統(tǒng)計

            公告

            統(tǒng)計系統(tǒng)

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            成人久久综合网| 色综合合久久天天综合绕视看| 国产精品久久久久一区二区三区 | 久久久WWW免费人成精品| 久久WWW免费人成—看片| 日本WV一本一道久久香蕉| 九九久久自然熟的香蕉图片| 久久亚洲av无码精品浪潮| 狠狠色丁香久久综合五月| 99精品国产99久久久久久97| 国产高潮国产高潮久久久91 | 久久久久亚洲av无码专区| 青青热久久国产久精品| 精品久久香蕉国产线看观看亚洲| 久久久久99精品成人片| 91精品国产91久久综合| 伊色综合久久之综合久久| 精品久久久久国产免费| 日韩久久久久久中文人妻| 亚洲国产一成人久久精品| 亚洲日韩中文无码久久| 国产成人久久精品麻豆一区| 国产Av激情久久无码天堂| 国色天香久久久久久久小说| 久久久久亚洲精品天堂久久久久久| 大伊人青草狠狠久久| 久久亚洲精品无码VA大香大香| 久久人人爽人人澡人人高潮AV| 欧美伊香蕉久久综合类网站| 久久精品国产久精国产思思| av色综合久久天堂av色综合在| 伊人久久无码精品中文字幕| 久久精品综合网| 色播久久人人爽人人爽人人片aV| 久久线看观看精品香蕉国产| 久久精品草草草| 精品久久久久久无码免费| 精品综合久久久久久88小说| 久久本道久久综合伊人| 亚洲午夜无码AV毛片久久| 久久只有这里有精品4|