频道栏目
首页 > 程序开发 > 软件开发 > Java > 正文
拓扑排序解成绩排名问题
2014-01-04 11:37:38         来源:LTianchao的专栏  
收藏   我要投稿

描述

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。

最后一行为“0 0”,表示输入结束,这一行无需处理。

输出

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

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(tot1)
			{
				flag=1;
			}
			if(sum==0)
			{
				flag=2;
				break;
			}
			mark[location]=1;
			for(j=0;j


点击复制链接 与好友分享!回本站首页
相关TAG标签 拓扑 成绩 问题
上一篇:Java Read CSV File In Java With OpenCSV library, int filed 属性为 int类型
下一篇:事件监听以及事件触发的简单实现流程
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站