洛谷P1127题解

传送锚点

摸鱼环节

词链

题目描述

如果单词 \(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

注意到，. 两边的字母一定是相同的。

现在给你一些单词，请你找到字典序最小的词链，使得每个单词在词链中出现且仅出现一次。注意，相同的单词若出现了 \(k\) 次就需要输出 \(k\) 次。

输入格式

第一行是一个正整数 \(n\)（\(1 \le n \le 1000\)），代表单词数量。

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

输出格式

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

样例 #1

样例输入 #1

6
aloha
arachnid
dog
gopher
rat
tiger

样例输出 #1

aloha.arachnid.dog.gopher.rat.tiger

提示

• 对于 \(40\%\) 的数据，有 \(n \leq 10\)；
• 对于 \(100\%\) 的数据，有 \(n \leq 1000\)。

最爱水题解的我又来蟹题解了，这道词链题生动形象的为我们展现了蓝水题的强度，于是这道图论题就被我们干掉了。

正片开始

观察到数据范围很小，说明能给暴力的空间比较充裕，但纯暴力肯定会挂。

1.考虑暴力

暴力的话，直接建立邻接表，将字符串\(a[i]\)数组进行排序后枚举每个点暴搜一下，这里展示搜索代码。

code：

void dfs(int u,string s,int cnt)//u当前遍历点的标号，s为答案，cnt为加入字符串的数量
{
    if(cnt==n)//递归出口
    {
        s[s.length()-1]=' ';
        cout<<s;
        exit(0);
    }
    for(auto v:g[u])//遍历邻接表
    {
        if(vis[v]==0)
        {
            vis[v]=1;
            dfs(v,s+a[v]+'.',cnt+1);
            vis[v]=0;
        }
    }
}

2.优化部分

我们从样例中可以发现，对于一条合法的答案，其一定为欧拉通路或欧拉回路。

一个点如果能作为起点，那其在字符串首出现次数一定比在字符串尾出现的次数多一，这样就可以对枚举起点处进行优化。

同时需特判回路的特殊情况。

code：

for(int i=1;i<=n;i++)
{
    in[a[i][0]]++;
    out[a[i][a[i].length()-1]]++;
}//统计每个字母作为首或尾出现的次数
for(int i=1;i<=n;i++)
{
    if(in[a[i][0]]==out[a[i][0]]+1)//满足条件才进入答案处理
    {
        vis[i]=1;
        dfs(i,a[i]+'.',1);
        vis[i]=0;
    }
}
vis[1]=1;
dfs(1,a[1]+'.',1);//特判欧拉回路
vis[1]=0;
cout<<"***"<<endl;//无解

完整代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+10;
int n,vis[N],in[N],out[N];
string a[N];
vector<int>g[N];
void dfs(int u,string s,int cnt)
{
    if(cnt==n)
    {
        s[s.length()-1]=' ';
        cout<<s;
        exit(0);
    }
    for(auto v:g[u])
    {
        if(vis[v]==0)
        {
            vis[v]=1;
            dfs(v,s+a[v]+'.',cnt+1);
            vis[v]=0;
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        in[a[i][0]]++;
        out[a[i][a[i].length()-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]) g[i].push_back(j);
    for(int i=1;i<=n;i++)
    {
        if(in[a[i][0]]==out[a[i][0]]+1)
        {
            vis[i]=1;
            dfs(i,a[i]+'.',1);
            vis[i]=0;
        }
    }
    vis[1]=1;
    dfs(1,a[1]+'.',1);
    vis[1]=0;
    cout<<"***"<<endl;
    return 0;
}

完结收工！！！！！

个人主页

看完点赞，养成习惯

\(\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\)