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、存在两个奇数度节点,那么答案是边权和加上这两个奇数度节点间的最短距离

发现现在越来越依赖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 阅读(317) 评论(0)  编辑 收藏 引用 所属分类: graph


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年2月>
2930311234
567891011
12131415161718
19202122232425
26272829123
45678910

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜