南阳市理工OJ 99 单词拼接(欧拉通路)
南阳理工OJ 99 单词拼接(欧拉通路)
描述
输入
第一行是一个整数N(0<N<20),表示测试数据的组数
每组测试数据的第一行是一个整数M,表示该组测试数据中有M(2<M<1000)个互不相同的单词,随后的M行,每行是一个长度不超过30的单词,单词全部由小写字母组成。
输出
如果存在拼接方案,请输出所有拼接方案中字典序最小的方案。(两个单词之间输出一个英文句号".")
如果不存在拼接方案,则输出
***
样例输入
样例输出
连接:http://acm.nyist.net/JudgeOnline/problem.php?pid=99
单词拼接
时间限制:3000 ms | 内存限制:65535 KB
难度:5
给你一些单词,请你判断能否把它们首尾串起来串成一串。
前一个单词的结尾应该与下一个单词的道字母相同。
如
aloha
dog
arachnid
gopher
tiger
rat
可以拼接成:aloha.arachnid.dog.gopher.rat.tiger
每组测试数据的第一行是一个整数M,表示该组测试数据中有M(2<M<1000)个互不相同的单词,随后的M行,每行是一个长度不超过30的单词,单词全部由小写字母组成。
如果不存在拼接方案,则输出
***
2 6 aloha arachnid dog gopher rat tiger 3 oak maple elm
aloha.arachnid.dog.gopher.rat.tiger ***
刚学了欧拉通路准备找题练手,就悲剧的找到了这个。虽然用思想挺简单,但是题目要求要按字典序排列,让我调试的好辛苦啊!最后没有办法还是找了位大牛(PIAOYI)帮忙。
贴下又烂又长的代码:
#include<cstdio> #include<iostream> #include<string> #include<cstring> #include<vector> #include<queue> using namespace std; const int maxcolor=26; int G[maxcolor+1][maxcolor+1]; vector<string> ans;//存放结果数组 priority_queue<string, vector<string>, greater<string> >mm[maxcolor+1][maxcolor+1];//按字典序排 int abs(int x) { return x>0?x:-x; } void euler(int u) { int uu,vv,flag=1; while(flag) { string str="{";//初始化str为最大 flag=0; for(int v=1;v<=maxcolor;v++)//找其中字典序最小的 { if(G[u][v]) { flag=1; if(str>mm[u][v].top()) { str=mm[u][v].top(); uu=u; vv=v; } } } if(flag)//继续深搜字典序最小的 { mm[uu][vv].pop(); G[uu][vv]--; euler(vv); ans.push_back(str);//最小的存在结果数组里面 } } } int f()//找起点函数 { int ru,chu,res=0,start=0; for(int i=1;i<=maxcolor;i++) { ru=chu=0; for(int j=1;j<=maxcolor;j++) { if(start==0&&G[i][j]!=0)start=i;//如果是欧拉图,起点就是第一个字母最小的那个单词 chu+=G[i][j]; ru+=G[j][i]; } res+=abs(chu-ru); if(chu>ru)start=i;//如果是半欧拉图,起点就是出度大一点的那个单词 } if(res>2)return -1;//如果不构成欧拉路,就跳出 return start; } int main() { // freopen("Input.txt","r",stdin); int T,start; string str,term; scanf("%d",&T); while(T--) { memset(G,0,sizeof(G)); int n; scanf("%d",&n); for(int i=1;i<=26;i++) for(int j=1;j<=26;j++) while(!mm[i][j].empty())mm[i][j].pop(); for(int i=0;i<n;i++) { cin>>str; int len=(int)str.size(); G[str[0]-'a'+1][str[len-1]-'a'+1]++;//存图,单词的开始为出度点,结尾为入度点 mm[str[0]-'a'+1][str[len-1]-'a'+1].push(str); } start=f(); if(start==-1) { printf("***\n"); continue; } ans.clear(); euler(start); if((int)ans.size()!=n)//如果单词没有找完,说明不连通,就输出*** { printf("***\n"); continue; } for(int i=ans.size()-1;i>=0;i--)//输出结果 { if(i!=0)cout<<ans[i]<<"."; else cout<<ans[i]; } cout<<endl; } return 0; }