首页 > 其他 > 详细

P1127 词链

时间:2018-02-14 15:27:40      阅读:103      评论:0      收藏:0      [点我收藏+]

标签:例子   gop   ***   bsp   -m   ret   ==   sort   spa   

题目描述

如果单词X的末字母与单词Y的首字母相同,则X与Y可以相连成X.Y。(注意:X、Y之间是英文的句号“.”)。例如,单词dog与单词gopher,则dog与gopher可以相连成dog.gopher。

另外还有一些例子:

dog.gopher

gopher.rat

rat.tiger

aloha.aloha

arachnid.dog

连接成的词可以与其他单词相连,组成更长的词链,例如:

aloha.arachnid.dog.gopher.rat.tiger

注意到,“.”两边的字母一定是相同的。

现在给你一些单词,请你找到字典序最小的词链,使得这些单词在词链中出现且仅出现一次。

输入输出格式

输入格式:

第一行是一个正整数n(1 ≤ n ≤ 1000),代表单词数量。

接下来共有n行,每行是一个由1到20个小写字母组成的单词

 

输出格式:

只有一行,表示组成字典序最小的词链,若不存在则只输出三个星号“***”。

 

输入输出样例

输入样例#1: 复制
6
aloha
arachnid
dog
gopher
rat
tiger
输出样例#1: 复制
aloha.arachnid.dog.gopher.rat.tiger

说明

对于40%的数据,有n≤10;

对于100%的数据,有n≤1000。

 

比较水的一题,就是有两个点会卡常……,最好先看看是否存在,是不是欧拉回路。

AC代码如下:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdlib>
using namespace std;
const int N=1000+5;
string a[N];
int ans[N],cnt[N],now,n;
vector<int>map[N];
bool vis[N];
void print()
{
    cout<<a[ans[1]];
    for(int i=2;i<=n;i++)
    cout<<.<<a[ans[i]];
    exit(0);
}
void dfs(int u)
{
    ans[++now]=u;
    vis[u]=1;
    if(now==n) print();
    for(int i=0;i<map[u].size();i++)
    if(!vis[map[u][i]]) dfs(map[u][i]);
    now--;
    vis[u]=0;
    return;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    if(i!=j&&a[i][a[i].length()-1]==a[j][0]) map[i].push_back(j);
    for(int i=1;i<=n;i++)
    cnt[a[i][a[i].length()-1]-a]--,cnt[a[i][0]-a]++;
    int flag=0,st=0;
    for(int i=0;i<=25;i++)
    {
        if(cnt[i]==1) flag++,st=i;
        if(cnt[i]==2) flag=2;
        if(flag==2) break;
    }
    if(flag==2) {printf("***");return 0;}
    
    for(int i=1;i<=n;i++)
     if((flag==1&&a[i][0]-a==st)||flag!=1) dfs(i);
    
    printf("***");
    return 0;
}

 

P1127 词链

标签:例子   gop   ***   bsp   -m   ret   ==   sort   spa   

原文:https://www.cnblogs.com/Alex-leaves/p/8448372.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号