The Postal Worker Rings Once

From:UVA, 117

Background

Graph algorithms form a very important part of computer science and have a lineage that goes back at least to Euler and the famous Seven Bridges of K?nigsberg problem. Many optimization problems involve determining efficient methods for reasoning about graphs.

This problem involves determining a route for a postal worker so that all mail is delivered while the postal worker walks a minimal distance, so as to rest weary legs.

The Problem

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.

The ``real-life‘‘ analogy concerns a postal worker who parks a truck at an intersection and then walks all streets on the postal delivery route (delivering mail) and returns to the truck to continue with the next route.

The cost of traversing a street is a function of the length of the street (there is a cost associated with delivering mail to houses and with walking even if no delivery occurs).

In this problem the number of streets that meet at a given intersection is called the degree of the intersection. There will be at most two intersections with odd degree. All other intersections will have even degree, i.e., an even number of streets meeting at that intersection.

The Input

The input consists of a sequence of one or more postal routes. A route is composed of a sequence of street names (strings), one per line, and is terminated by the string ``deadend‘‘ which is NOT part of the route. The first and last letters of each street name specify the two intersections for that street, the length of the street name indicates the cost of traversing the street. All street names will consist of lowercase alphabetic characters.

For example, the name foo indicates a street with intersections f and o of length 3, and the name computer indicates a street with intersections c and r of length 8. No street name will have the same first and last letter and there will be at most one street directly connecting any two intersections. As specified, the number of intersections with odd degree in a postal route will be at most two. In each postal route there will be a path between all intersections, i.e., the intersections are connected.

The Output

For each postal route the output should consist of the cost of the minimal tour that visits all streets at least once. The minimal tour costs should be output in the order corresponding to the input postal routes.

Sample Input

one
two
three
deadend
mit
dartmouth
linkoping
tasmania
york
emory
cornell
duke
kaunas
hildesheim
concord
arkansas
williams
glasgow
deadend

Sample Output

11
114

 题目大意：

每个字符串的首字母和尾字母代表街道的两个路口，是双向的，字符串的长度是街道的长度，邮递员需要穿过所有的街道，求邮递员走的最短路径。

解题思路：

当所有点的入度都是偶数说明成环，直接所有边的边长相加即可。若有奇数度 ，则是所有边长相加以后再加上从奇度点到奇度点的最短路径。

SPFA算法+邻接表。

代码：

#include<iostream>
#include<string>
#include<cstdio>
#include<queue>
using namespace std;

const int maxn=30;
const int maxm=4000000;

struct edge{
    int u,v,w,next;
    edge(int u0=0,int v0=0,int w0=0,int next0=0){
        u=u0,v=v0,w=w0,next=next0;
    }
}e[maxm];

string str0;
int dist[maxn],head[maxn],indeg[maxn],cnt,sumDist,from,des;
bool isInQueue[maxn];

void initial(){
    from=des=0;
    cnt=0;
    sumDist=0;
    for(int i=0;i<maxn;i++){
        dist[i]=1<<30;//不要写成31，不然就爆掉了。
        head[i]=-1;
        isInQueue[i]=false;
        indeg[i]=0;
    }
}

void adde(int u,int v,int w){
    e[cnt].u=u,e[cnt].v=v,e[cnt].w=w;
    e[cnt].next=head[u],head[u]=cnt++;//邻接表储存图。
}

void input(){
    while(str0!="deadend"){
        int p=str0[0]-'a',q=str0[str0.length()-1]-'a';
        indeg[p]++;
        indeg[q]++;
        adde(p,q,str0.length());
        adde(q,p,str0.length());//双向边
        sumDist+=str0.length();
        cin>>str0;
    }
}

void outResult(){printf("%d\n",sumDist);}

void spfa(){
    queue <int> q;
    int s;
    dist[from]=0;
    q.push(from);
   // cntIn[from]++;
    isInQueue[from]=true;
    while(!q.empty()){
        s=q.front();
        q.pop();
        for(int i=head[s];i!=-1;i=e[i].next){
            if(dist[e[i].v]>dist[e[i].u]+e[i].w){
                dist[e[i].v]=dist[e[i].u]+e[i].w;
                if(!isInQueue[e[i].v]){
                    q.push(e[i].v);
                    //cntIn[e[i].v]++;
                    //if(cntIn[e[i].v]>sqrt(n)) return;//判是否负环。
                    isInQueue[e[i].v]=true;
                }
            }
        }
        isInQueue[s]=false;
    }
}

void solve(){
    bool isOdd=false;
    for(int i=0;i<26;i++){
        if(indeg[i]&1&&!isOdd){
            isOdd=true;
            from=i;
            continue;
        }
        if(indeg[i]&1&&isOdd){des=i;break;}
    }
    if(!isOdd) return;
    spfa();
    sumDist+=dist[des];
}

int main(){
    while(cin>>str0){
        initial();
        input();
        solve();
        outResult();
    }
    return 0;
}

one
two
three
deadend
mit
dartmouth
linkoping
tasmania
york
emory
cornell
duke
kaunas
hildesheim
concord
arkansas
williams
glasgow
deadend

11
114

The Postal Worker Rings Once(UVA 117)最短路径—SPFA算法+邻接表