洛谷P1127-词链

Problem 洛谷P1127-词链

Accept: 256 Submit: 1.3k
Time Limit: 1000 mSec Memory Limit : 128MB

Problem Description

如果单词 XXX 的末字母与单词 YYY 的首字母相同，则 XXX 与 YYY 可以相连成 X.YX.YX.Y 。（注意： XXX 、 YYY 之间是英文的句号“.”）。例如，单词dog与单词gopher，则dog与gopher可以相连成dog.gopher。

另外还有一些例子：

dog.gopher

gopher.rat

rat.tiger

aloha.aloha

arachnid.dog

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

aloha.arachnid.dog.gopher.rat.tiger

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

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

Input

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

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

Output

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

Sample Input

6
aloha
arachnid
dog
gopher
rat
tiger

Sample Output

aloha.arachnid.dog.gopher.rat.tiger

题目链接：https://www.luogu.org/problemnew/show/P1127

这个题做的很差，感觉很简单，可能还是学艺不精。

剪枝的方式还是值得一提的，这个题乍一看上去没有剪枝的思路，当把整个链和欧拉路径联系起来思路自然就出来了。

统计每个字符串首尾字母出现次数，在首位出现就++，在末位就--，如果能够连成词链，那么每个字母的统计值只能位0或1，并且如果有1只能是同时有两个，

据此可以作为充要条件判断是否有解。与此同时，一个剪枝的方式也就出来了，如果是一个+1，一个-1的情况，那么+1的那个必定时开头，避免了很多无用的搜索。

字典序的问题还是非常简单的，先按字典序sort一下，链式前向星存图，因此加边的时候倒着来就好，遇到词链就输出，退出程序。

还有一个神奇的地方，就是abc和abcb的情况，虽然abc < abcb,但是如果有一个c、b 接上去就成了abcc...、abcbb...

好像用上述算法还是有问题的，原来还听老师讲过一个类似的题，也是这种情况下有点问题，不过都能AC...

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <string>

 #include <stack>

 #include <algorithm>

 using namespace std;

 const int maxn = +;

 const int maxm = maxn*maxn;

 int n,tot,head[maxn];

 int len[maxn];

 bool vis[maxn];

 string str[maxn];

 struct Edge{

     int to,next;

     Edge(int to = ,int next = ) : to(to),next(next) {}

 }edge[maxm<<];

 void AddEdge(int u,int v){

     edge[tot].to = v;

     edge[tot].next = head[u];

     head[u] = tot++;

 }

 int top,sta[maxn<<];

 void output(){

     cout << str[sta[]];

     for(int i = ;i <= n;i++){

         printf(".");

         cout << str[sta[i]];

     }

     cout << endl;

     exit();

 }

 void dfs(int u){

     vis[u] = true;

     sta[++top] = u;

     for(int i = head[u];i != -;i = edge[i].next){

         int v = edge[i].to;

         if(!vis[v]) dfs(v);

     }

     if(top == n) output();

     vis[u] = false;

     top--;

 }

 const int kind = ;

 int con[maxn];

 int main()

 {

     //freopen("input.txt","r",stdin);

     cin >> n;

     for(int i = ;i <= n;i++){

         cin >> str[i];

     }

     sort(str+,str++n);

     top = ;

     memset(head,-,sizeof(head));

     memset(vis,false,sizeof(vis));

     memset(con,,sizeof(con));

     for(int i = ;i <= n;i++){

         len[i] = str[i].size();

     }

     for(int i = ;i <= n;i++){

         for(int j = n;j >= ;j--){

             if(i!=j && str[i][len[i]-] == str[j][]){

                 AddEdge(i,j);

             }

         }

     }

     for(int i = ;i <= n;i++){

         con[str[i][]-'a']++;

         con[str[i][len[i]-]-'a']--;

     }

     int head = -,cnt = ,_cnt = ;

     for(int i = ;i < kind;i++){

         if(con[i] == ){

             head = i;

             cnt++;

         }

         else if(con[i] == -){

             _cnt++;

         }

      }

      if(cnt== && _cnt==){

         for(int i = ;i <= n;i++){

             dfs(i);

         }

      }

      else if(cnt== && _cnt==){

         for(int i = ;i <= n;i++){

             if(str[i][]-'a' == head) dfs(i);

         }

      }

      printf("***\n");

     return ;

 }

词链