题目链接：http://poj.org/problem?id=2337 题意：问你所有的字符串能否首尾相连在一起，如果能，输出字典序最小的那一串东西，否则输出* 解析：对于输入所有字符串先排个序，然后逆序建图，这样就搜的时候就是优先选择字典序小的字符串，然后就是判是否符合题意，搜的时候记录一下结果
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <string> using namespace std; const int maxn = 5005; struct node { int flag; int next; int to; int id; }edge[maxn]; int head[maxn],cnt,cur; int vis[maxn],out[maxn],in[maxn]; int ans[maxn]; string a[maxn]; void init() { memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); memset(out,0,sizeof(out)); memset(in,0,sizeof(in)); cnt = cur = 0; } void addEdge(int from,int to,int index) { edge[cnt].id = index; edge[cnt].to = to; edge[cnt].next = head[from]; edge[cnt].flag = 0; head[from] = cnt++; } void dfs(int i) { for(int j=head[i];j!=-1;j = edge[j].next) { if(!edge[j].flag) { edge[j].flag = 1; dfs(edge[j].to); ans[cur++] = edge[j].id; } } } int main(void) { int t,n; scanf("%d",&t); while(t--) { init(); scanf("%d",&n); for(int i=0;i<n;i++) cin>>a[i]; sort(a,a+n); int start = maxn; for(int i=n-1;i>=0;i--) { int len = a[i].length(); int s = a[i][0]-'a'; int t = a[i][len-1]-'a'; addEdge(s,t,i); vis[s] = vis[t] = 1; out[s]++,in[t]++; if(s<start) start = s; if(t<start) start = t; } int flag = 1,scnt = 0,ecnt = 0; for(int i=0;i<100;i++) { if(out[i]!=in[i]) { if(out[i]-in[i]==1) start = i,scnt++; else if(out[i]-in[i]==-1) ecnt++; else flag = 0; } } if(flag&&((scnt==0 && ecnt==0)||(scnt==1 && ecnt==1))) { dfs(start); if(cur!=n) puts("***"); else { for(int i=cur-1;i>=0;i--) { if(i!=cur-1)printf("."); cout<<a[ans[i]]; } puts(""); } } else puts("***"); } return 0; }