题解 P1127 【词链】

· · 题解

看到这题，一般的第一个想法就是暴力搜索。

根据数据范围，搜索应该能拿到 40 分左右的成绩。

下面我们考虑正解。

我们发现，一个单词在词链中与哪些单词拼接，只与这个单词开头和末尾的两个字符有关！

别看这个性质很普通，这恰好是我们数学建模的入手点！

如何数学建模？考虑把单词开头字母向单词结尾字母连边，我们可以得到一个有向图。这时候再看题目，这题就变成了求欧拉路径的问题了。

想到这里，你已经成功了一半了。下面开始考虑判断无解和寻找路径起点的问题。

关于有向图的欧拉路径起点，可以用如下方法寻找：

把一个点的度记为这个点的出度减去这个点的入度。一个有向图存在欧拉路径，则这个路径的起点的度必为 1,终点的度必为 -1，其余点的度为 0。如果所有点的度都是 0，则变成欧拉回路，可以从任意点开始搜索。

另外，还要判断无解。无解的情况就是图不连通。有一个判无解的简单方法：搜索完成后，判断是否所有的边都被搜过，如果没有，无解。

另外，题目要求要字典序最小的答案。对此，可以把输入的单词排序后连边。需要注意的是，如果是用边链表存边的，需要倒序连边，才能保证字典序最小。然后如果遇到欧拉回路，则找存在的字母中字典序最小的开始搜索即可。

那么这题就做完了，下面是代码：

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#define ll long long
#define rgt register int
using namespace std;
const int mxn = 1010;
string str[mxn],outans[mxn];
int tot,lst[30],nxt[mxn],to[mxn],bh[mxn],d[mxn],lans;
bool use[mxn];

inline void add(int x,int y,int b){
    tot++;
    to[tot]=y;
    bh[tot]=b;   //存这条边对应的字符串编号
    d[x]++;
    d[y]--;   //计算点度
    nxt[tot]=lst[x];
    lst[x]=tot;
}   //加边函数

void dfs(int g){  //搜索函数
    for(rgt i=lst[g];i;i=nxt[i]){
        if(!use[bh[i]]){  //找到一条未使用的边
            use[bh[i]]=true;  //标记
            dfs(to[i]);
            lans++;  //倒序存答案
            outans[lans]=str[bh[i]];
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    int n,st;
    cin>>n;
    for(rgt i=1;i<=n;i++)
        cin>>str[i];   //读入数据

    sort(str+1,str+1+n);  //排序
    st=str[1][0]-'a'+1;  //先把存在的字典序最小的字母作为起点，如果是欧拉回路，则从这个起点切入

    for(rgt hd,tl,i=n;i>=1;i--){
        hd=str[i][0]-'a'+1;  //首字母
        tl=str[i][str[i].size()-1]-'a'+1;  //尾字母
        add(hd,tl,i);  //连边
    }  

    for(rgt i=1;i<=26;i++)
        if(d[i]==1){  //是欧拉路径，更新起点
            st=i;
            break;
        }

    dfs(st);

    for(rgt i=1;i<=n;i++)
        if(!use[i]){
            cout<<"***";
            return 0; 
        } //如果没有使用所有边，无解

    for(rgt i=lans;i>1;i--)
        cout<<outans[i]<<".";
    cout<<outans[1];  //输出答案

    return 0;
}