## 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、所有节点的度都为偶数，那么答案就是所有边权和
2、存在两个奇数度节点，那么答案是边权和加上这两个奇数度节点间的最短距离

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        {
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 阅读(306) 评论(0)  编辑 收藏 引用 所属分类: graph

 只有注册用户登录后才能发表评论。 【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！ 相关文章:
 < 2011年1月 >
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

• 随笔 - 183
• 文章 - 2
• 评论 - 27
• 引用 - 0

•

• 积分 - 49453
• 排名 - 449