南阳理工OJ 99 单词拼接（欧拉通路）

连接：http://acm.nyist.net/JudgeOnline/problem.php?pid=99

单词拼接

时间限制：3000 ms  |  内存限制：65535 KB

难度：5

 

描述

给你一些单词，请你判断能否把它们首尾串起来串成一串。

前一个单词的结尾应该与下一个单词的道字母相同。

如

 

aloha

dog

arachnid

gopher

tiger

rat

 

可以拼接成：aloha.arachnid.dog.gopher.rat.tiger

 

 

输入

第一行是一个整数N(0<N<20)，表示测试数据的组数
每组测试数据的第一行是一个整数M,表示该组测试数据中有M(2<M<1000)个互不相同的单词，随后的M行，每行是一个长度不超过30的单词,单词全部由小写字母组成。

输出

如果存在拼接方案，请输出所有拼接方案中字典序最小的方案。(两个单词之间输出一个英文句号".")
如果不存在拼接方案，则输出
***

样例输入

2
6
aloha
arachnid
dog
gopher
rat
tiger
3
oak
maple
elm

样例输出

aloha.arachnid.dog.gopher.rat.tiger
***

 

刚学了欧拉通路准备找题练手，就悲剧的找到了这个。虽然用思想挺简单，但是题目要求要按字典序排列，让我调试的好辛苦啊！最后没有办法还是找了位大牛（PIAOYI）帮忙。

贴下又烂又长的代码：

 

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

const int maxcolor=26;
int G[maxcolor+1][maxcolor+1];
vector<string> ans;//存放结果数组
priority_queue<string, vector<string>, greater<string> >mm[maxcolor+1][maxcolor+1];//按字典序排

int abs(int x)
{
    return x>0?x:-x;
}

void euler(int u)
{
    int uu,vv,flag=1;
    while(flag)
    {
        string str="{";//初始化str为最大
        flag=0;
        for(int v=1;v<=maxcolor;v++)//找其中字典序最小的
        {
            if(G[u][v])
            {
                flag=1;
                if(str>mm[u][v].top())
                {
                    str=mm[u][v].top();
                    uu=u;
                    vv=v;
                }
            }
        }
        if(flag)//继续深搜字典序最小的
        {
               mm[uu][vv].pop();
               G[uu][vv]--;
               euler(vv);
               ans.push_back(str);//最小的存在结果数组里面
        }
    }
}

int f()//找起点函数
{
    int ru,chu,res=0,start=0;
    for(int i=1;i<=maxcolor;i++)
    {
        ru=chu=0;
        for(int j=1;j<=maxcolor;j++)
        {
            if(start==0&&G[i][j]!=0)start=i;//如果是欧拉图，起点就是第一个字母最小的那个单词
            chu+=G[i][j];
            ru+=G[j][i];
        }
        res+=abs(chu-ru);
        if(chu>ru)start=i;//如果是半欧拉图，起点就是出度大一点的那个单词
    }
    if(res>2)return -1;//如果不构成欧拉路，就跳出
    return start;
}

int main()
{
//    freopen("Input.txt","r",stdin);
    int T,start;
    string str,term;
    scanf("%d",&T);
    while(T--)
    {
        memset(G,0,sizeof(G));
        int n;
        scanf("%d",&n);
        for(int i=1;i<=26;i++)
              for(int j=1;j<=26;j++)
                     while(!mm[i][j].empty())mm[i][j].pop();
        for(int i=0;i<n;i++)
        {
            cin>>str;
            int len=(int)str.size();
            G[str[0]-'a'+1][str[len-1]-'a'+1]++;//存图，单词的开始为出度点，结尾为入度点
            mm[str[0]-'a'+1][str[len-1]-'a'+1].push(str);
        }
        start=f();
        if(start==-1)
        {
            printf("***\n");
            continue;
        }
        ans.clear();
        euler(start);
        if((int)ans.size()!=n)//如果单词没有找完，说明不连通，就输出***
        {
            printf("***\n");
            continue;
        }
        for(int i=ans.size()-1;i>=0;i--)//输出结果
        {
            if(i!=0)cout<<ans[i]<<".";
            else cout<<ans[i];
        }
        cout<<endl;
    }
    return 0;
}