拓扑排序解成绩排名问题

描述

2013“华为杯”南京邮电大学大学生团体歌唱大赛比赛形式为：大赛分为多轮，每一轮随机选择参赛团体进行两两PK赛。当根据多轮多场的PK赛成绩能够确定排名次序时，大赛结束。

我们将问题进行简化，从1开始按递增顺序给每一个参赛团体分配一个整数编号，每个参赛团体在比赛期间表现出的歌唱水平各不相同且稳定不变，每场PK赛成绩必定胜负。给定已记录的多场PK赛成绩，请你根据胜负关系确定大赛是否应该结束，并且能够排除记录出现错误的情形。

举一个例子，共有三个参赛团体参加大赛，如果参赛团体1在PK赛中胜参赛团体3、参赛团体2在PK赛中胜参赛团体1，则可知参赛团体2的成绩比参赛团体3的成绩排名高，也说明参赛团体2的歌唱水平一定高于参赛团体3的歌唱水平；如果参赛团体1在PK赛中胜参赛团体2、参赛团体2在PK赛中胜参赛团体3、参赛团体3在PK赛中胜参赛团体1，则出现这种情形说明存在明显的记录错误。

输入

输入包括多个测试用例。

每个测试用例包括C+1行，第1行给出参赛团体总数M、已知PK赛成绩的场次数C；接下来有C行，每一行先后给出两个参赛团体编号p和q，表示编号为p的参赛团体在PK赛中胜编号为q的参赛团体；这里1≤M≤1000，1≤C≤500000，1≤p≤M，1≤q≤M，p≠q。

输出

针对问题输入中的每个测试用例，输出一行字符串，具体规定如下：

l 根据已记录的PK赛成绩能够确定排名次序时，则输出字符串Competition over

l 根据已记录的PK赛成绩还不能确定排名次序时，则输出字符串Competition continue

l 根据已记录的PK赛成绩不可能确定排名次序时，则输出字符串Wrong Results

样例输入

4 3
4 3
3 2
2 1
4 3
4 3
2 3
1 4
4 3
4 3
1 4
3 1
0 0

样例输出

Competition over
Competition continue
Wrong Results

本题我的最初想法是这样的: 利用二维数组mark[][] 保存点之间的相连关系. 若mark[i][j] =1,则表明 i到j之间有一条通路,即i>j .

在没加入一条边s-t时,更新mark, 使能到达s的点也能到达t

每连接两个本未相连的点时tot++, tot保存连线数.

判断时,首先检查是否存在点对 i ,j 使mark[i][j]==mark[j][i]==1 ,若存在,则出现矛盾情况 wrong result

如果不满足上述条件, 则检查tot. 若tot不等于m*(m-1)/2 则连线不足, 必须继续比赛.

不满足上述两种情况, 则比赛结束.

虽然思路很顺,做法貌似可行,样例输出也对,可是啊,提交时一直是超时啊,怎么交都是超时啊,已经各种优化各种剪枝了啊. 就在崩溃之时,在一个类似题目的回帖中看到四个大字"拓扑排序" ! 林光一闪有木有, 醍醐灌顶有木有,之前的作法弱爆了有木有!

如果出现死循环则 wrong results, 出现多于一个入度为0的点则 competition continue(因为同时度为0的点之间无法决胜), 这道题简直为拓扑为生啊.我感觉我也要为拓扑为生啊有没有啊.

要注意的是这道题矛盾情况是要压倒平局情况的.也就是根据题目描述,如果同时出现比分矛盾和平局,那么结果应该为矛盾,此时已经没有必要再continue了!

所以发现平局时设置flag为1,但并不退出循环. 如果后面发现矛盾是要flag=2来覆盖掉的.

带马!

#include
  
   
#include
   
     using namespace std; class node { public: int next[1001]; }; int ls[1001],lt[1001],mark[1001]; int main() { // freopen("1983.txt","r",stdin); int m,c; int flag,location,tot,sum; int i,j,s,t; while(cin>>m>>c) { memset(ls,0,sizeof(ls)); memset(lt,0,sizeof(lt)); memset(mark,0,sizeof(mark)); node *p=new node[m+1]; tot=0; if(m==0&&c==0) break; for(i=0;i
    
     >s>>t; scanf("%d%d",&s,&t); p[s].next[lt[s]]=t; lt[s]++; ls[t]++; } flag=0; while(tot
     
      1) { flag=1; } if(sum==0) { flag=2; break; } mark[location]=1; for(j=0;j