【题解】单词接龙 搜索 NOIP2000 提高组

传送门＝￣ω￣＝

思路：建立有向图！对于输入的字符串 s[i] 和 s[j]，dis[i][j] 表示字符串 s[j] 接在 s[i] 后面时的重叠部分的长度。用函数 con(i,j) 计算 dis[i][j] 的值（注意！dis[i][j] 不一定等于 dis[j][i]！）。在函数 con 中，我采用了 STL 的双端队列（deque），它可以从容器首位插入元素，并且支持==比较运算。然后再用 dfs 找最长路，把字符串 s[i] 和 s[j] 接起来产生的长度为 s[i] 的长度＋s[j] 的长度-dis[i][j]。

特别注意！一开始我就被这个坑了！每个单词可以用２次！

代码：

#include <bits/stdc++.h>
using namespace std;
int n,ans,dis[25][25],book[25];
string s[25];
char c;
void con(int u,int v)
{
    int lim=min(s[u].length(),s[v].length());
    deque<char> scp[2];
    for(int i=1;i<lim;i++)
    {
        scp[0].push_front(s[u][s[u].length()-i]),scp[1].push_back(s[v][i-1]);
        if(scp[0]==scp[1]){dis[u][v]=i;break;}
    }
}
void dfs(int u,int d)
{
    ans=max(ans,d),book[u]++;
    for(int i=1;i<=n;i++)if(book[i]<2&&dis[u][i])dfs(i,d+s[i].length()-dis[u][i]);
    book[u]--;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>s[i];
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)con(i,j);
    cin>>c;
    for(int i=1;i<=n;i++)
        if(s[i][0]==c)
            dfs(i,s[i].length());
    cout<<ans;
    return 0;
}

至于 vjudge 上的 HRBUST – 1213，有多组数据。。。
所以一开始我蜜汁WA。。。
代码：

#include <bits/stdc++.h>
using namespace std;
int n,ans,dis[25][25],book[25];
string s[25];
char c;
void con(int u,int v)
{
    int lim=min(s[u].length(),s[v].length());
    deque<char> scp[2];
    for(int i=1;i<lim;i++)
    {
        scp[0].push_front(s[u][s[u].length()-i]),scp[1].push_back(s[v][i-1]);
        if(scp[0]==scp[1]){dis[u][v]=i;break;}
    }
}
void dfs(int u,int d)
{
    ans=max(ans,d),book[u]++;
    for(int i=1;i<=n;i++)
        if(book[i]<2&&dis[u][i])dfs(i,d+s[i].length()-dis[u][i]);
    book[u]--;
}
int main()
{
    while(ans=0,memset(dis,0,sizeof(dis)),memset(book,0,sizeof(book)),cin>>n)
    {
        for(int i=1;i<=n;i++)cin>>s[i];
        for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)con(i,j);
        cin>>c;
        for(int i=1;i<=n;i++)if(s[i][0]==c)dfs(i,s[i].length());
        cout<<ans<<endl;
    }
    return 0;
}