Q：拓扑排序用于解决什么问题？
烦人的幻灯片 题目描述 李教授于今天下午做一个非常重要的演讲。不幸的是他不是一个非常爱整洁的人，他把自己做演讲要用的幻灯片随便堆放在一起。因此，演讲之前他不得不去整理这些幻灯片。做为一个讲求效率的学者，他希望尽可能简单地完成它。情况是这样，教授这次演讲一共要用n张幻灯片（n<=26），这n张幻灯片按照演讲要使用的顺序已经用数字1，2，…，n在上面编上了号。因为幻灯片是透明的，所以我们不能一下子看清每一个数字所对应的幻灯片。
现在我们用大写字母A，B，C，。。。再次把幻灯片依次编号。你的任务是编写一个程序，把幻灯片的数字编号和字母编号对应起来，显然这种对应应该是唯一的；若出现多种对应的情况或是某些数字编号和字母对应不起来，我们就称对应是无法实现的。
输入 第一行：只有一个数n，表示有n张幻灯片。
接下来的n行：包括4个整数Xmin，Xmax，Ymin，Ymax（整数之间用空格分开），为幻灯片的坐标（该区域为幻灯片），这n张幻灯片按其在输入文件中出现的顺序从前到后依次编号为A，B，C，…再接下来的n行依次为n个数字编号的坐标X，Y，显然在幻灯片之外是不会有数字的。
输出 若是对应可以实现，你的输出应该包括n行，每一行为一个字母和一个数字，中间以一个空格隔开，并且各行以字母的升序排列，注意输出的字母要大写并且顶格；反之，若是对应无法实现，在第一行顶格输出None即可。行首行末无多余空格。
样例输入 4 6 22 10 20 4 18 6 16 8 20 2 18 10 24 4 8 9 15 19 17 11 7 21 11 样例输出 A 4 B 1 C 2 D 3
这个幻灯片够烦人的。 本题的关键在于如何构图，构造拓扑排序的模型。 题目大意为若干部分（或全部）重合二维的矩形中分布有若干个点，一个矩形和一个点如小王子和狐狸一样彼此唯一拥有，让你进行分配，无法分配输出“None”。 建模：统计每张幻灯片中有几个点（或每个点在几张幻灯片中），每次确定只拥有一个点的幻灯片。可以想到用拓扑排序。 代码如下:
#include<cstdio> using namespace std; bool f=true; int n,num,top,matrix[30][30],ru[30],chu[30],zhan[30],ans[30]; struct Photo{//幻灯片 int Xmin,Xmax,Ymin,Ymax; }; Photo photo[30]; struct Node{ int x,y; }; Node node[30]; void PRINT() { for (int i=1; i<=n-1; i++) printf("%c %d\n",i+'A'-1,ans[i]);//强制类型转换的技巧 printf("%c %d",n+'A'-1,ans[n]); } int main() { scanf("%d",&n); for (int i=1; i<=n; i++) scanf("%d%d%d%d",&photo[i].Xmin,&photo[i].Xmax,&photo[i].Ymin,&photo[i].Ymax); for (int i=1; i<=n; i++) scanf("%d%d",&node[i].x,&node[i].y); for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) if (node[j].x>=photo[i].Xmin&&node[j].x<=photo[i].Xmax&&node[j].y>=photo[i].Ymin&&node[j].y<=photo[i].Ymax) { matrix[i][j]=1;//不能用bush表存,不好操作.第i张幻灯片指向第j个点 chu[i]++; } for (int i=1; i<=n; i++) ru[i]=chu[i]-1;//入度为出度-1 while (num!=n) { int ss=0;//记录本次入度为0的点的个数，用来判断是否有环 for (int i=1; i<=n; i++) { if (ru[i]==0) { num++; ss++; zhan[++top]=i; for (int j=1; j<=n; j++) if (matrix[i][j]) { ans[i]=j; break; }//break 一点小优化:入度为0的点出度为1 ru[i]=0x7fffffff; //相当于开一个bool数组，每个点只入栈一次 } } if (ss==0) { f=false; break; } for (int i=1; i<=ss; i++)//去掉相连的边 { int now=zhan[top]; top--; for (int j=1; j<=n; j++) if (matrix[j][ans[now]]) { matrix[j][ans[now]]=0; ru[j]--; } } } if (f) PRINT(); else printf("None"); return 0; } /* 4 6 22 10 20 4 18 6 16 8 20 2 18 10 24 4 8 9 15 19 17 11 7 21 11 */病毒 题目描述 有一天，小y突然发现自己的计算机感染了一种病毒！还好，小y发现这种病毒很弱，只是会把文档中的所有字母替换成其他字母，但并不改变顺序，也不会增加和删除字母。
现在怎么恢复原来的文档呢？小y很聪明，他在其他没有感染病毒的机器上，生成了一个由若干单词构成的字典，字典中的单词是按照字母顺序排列的，他把这个文件拷贝到自己的机器里，故意让它感染上病毒，他想利用这个字典文件原来的有序性，找到病毒替换字母的规律，再用来恢复其他文档。
现在你的任务是：告诉你被病毒感染了的字典，要你恢复一个字母串。
输入 第1行为整数K（<50000），表示字典中的单词个数。
以下K行，是被病毒感染了的字典，每行一个单词。
最后一行是需要你恢复的一串字母。
所有字母均为小写。
输出 输出仅一行：为恢复后的一串字母，当然也有可能出现字典不完整、甚至字典是错的情况，这时请输出一个0。
样例输入 6 cebdbac cac ecd dca aba bac cedab 样例输出 abcde
好吧我承认我这道题死于题意。“字典中的单词是按照字母顺序排列的”这句话智障的我理解成了单词中的每一个单词的字母是按照“abcde….”的顺序出现的，然而想想英语课本Words and Expressions in Each Unit 中各个单词按首字母排序，首字母相同的按照第二个字母排，以此类推。。 明白这个原理，就很容易构建出拓扑排序的模型了：将相邻的两个单词从首字母开始往后找，遇到不同的字母就建立边，然后马上break；对图进行topsort，得到的拓扑序列就是“密码”：每个字母在ans中的位置即为正确的字母。 但是还需要注意一个问题——有哪几点需要输出“0”： （1）在构图的时候，不相同的两组单词不能有重复，否则就违背了“这个字典文件原来的有序性”原则，所以建一个matrix[][]进行标记； （2）AOV网中最关键的一点是不能有环，否则不能形成拓扑序列； （3）待更正的单词中有字母在“字典”中查不到。 （4）在拓扑排序的过程中，每一轮只能有且只有一个入度为0的点，即拓扑序列是唯一的
#include<iostream> #include<cstdio> #include<algorithm> #include<cstdlib> #include<string> #include<cstring> using namespace std; string st[50001]; char ch[101]; bool matrix[30][30]; int n,num_edge,top,num,tot,maxchar,ru[50001],zhan[50001],head[30],ans[30],t;//ans用来存拓扑序列 struct Edge{ int next,to; }; Edge edge[300]; void add_edge(int from,int to) { edge[++num_edge].next=head[from]; edge[num_edge].to=to; head[from]=num_edge; } void topsort() { while (num<maxchar)//<maxchar 而不是<n { int ss=0;//判断是否有环 for (int i=1; i<=maxchar; i++) if (ru[i]==0) { num++; ss++; zhan[++top]=i; ans[++tot]=i; ru[i]=0x7fffffff;//标记 } if (ss!=1) { printf("0"); exit(0); }//有环 while (top!=0) { int now=zhan[top]; top--; for (int i=head[now]; i!=0; i=edge[i].next) ru[edge[i].to]--; } } } int main() { freopen("virus.in","r",stdin); freopen("virus.out","w",stdout); scanf("%d",&n); for (int i=1; i<=n; i++) { cin>>st[i]; for (int j=1; j<=st[i].length(); j++)//注意下标从0开始 if (st[i][j]-96>maxchar) maxchar=st[i][j]-96; } for (int i=1; i<=n-1; i++) { int j=i+1; for (int k=0; k<=min(st[i].length(),st[j].length())-1;/*两个单词中长度较小的一个*/ k++) { if (st[i][k]!=st[j][k]) { //由于形成的拓扑序列前面一定比后面小。所以不能有重复（前者），也不能形成环（后者） if (matrix[st[i][k]-96][st[j][k]-96]||matrix[st[j][k]-96][st[i][k]-96]) { printf("0"); return 0; } add_edge(st[i][k]-96,st[j][k]-96); ru[st[j][k]-96]++; matrix[st[i][k]-96][st[j][k]-96]=1; break;//不要忘记break，每次只取一个字母 } } } topsort(); getchar();//读掉回车 gets(ch); int len=strlen(ch); for (int i=0; i<=len; i++)//i从0开始 if (ch[i]-96>maxchar) { printf("0"); return 0; } for (int i=0; i<=len-1; i++) for (int j=1; j<=tot; j++) if (ch[i]-96==ans[j]) printf("%c",j+96); return 0; } /* 6 cebdbac cac ecd dca aba bac cedab */