Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

原来 当拓扑排序不唯一(当然也就不确定)的时候 还要判断是否有环! nightKnight 2004-09-15 02:38:00.0 Problem 1094

Posted by Judas at 2006-04-13 22:11:31 on Problem 1094
In Reply To:1094求助 Posted by:zouyuanrenren at 2006-04-13 21:53:39
> 感觉算法没有问题
> 依次读入关系,在邻接矩阵中加入边,按出度进行拓扑排序
> 找到出度为0的点
> 若有多个则尚无法排序
> 若没有,则存在环,有矛盾
> 若只有一个,将其删除,同时删除所有指向它的边,并将起加到输出序列中
> 循环,再次找出度为0的点
> 直到所有点都排到输出序列中,即可以排序
> 试了很多测试数据,也找不到错误
> 请各位帮忙看看问题在哪里
> 
> #include <iostream>
> 
> using namespace std;
> 
> short matrix[26][26];
> int n, m;
> int seq[26];
> 
> int hamilton() 
> // if can be sorted, return 1 
> // if inconsistency, return -1
> // other, return 0;
> {
> 	short image[26][26];
> 	bool mask[26];
> 	int i, j;
> 	int finish = 0;
> 	int leastnum = 0, least, less;
> 	// copy the matrix and find the least
> 	for(i = 0;i < n;i ++)
> 	{
> 		mask[i] = 1;
> 		less = 0;
> 		for(j = 0;j < n;j ++)
> 		{
> 			image[i][j] = matrix[i][j];
> 			less += matrix[i][j];
> 		}
> 		if(less == 0)
> 		{
> 			leastnum ++;
> 			least = i;
> 		}
> 	}
> 	if(leastnum == 0) // circuit found
> 		return -1;
> 	if(leastnum > 1)
> 		return 0;
> 	while(leastnum == 1)
> 	{
> 		seq[finish] = least;
> 		finish ++;
> 		for(i = 0;i < n;i ++)
> 			image[i][least] = 0;
> 		mask[least] = 0;
> 		leastnum = 0;
> 		for(i = 0;i < n;i ++)
> 		{
> 			less = 0;
> 			if(mask[i] == 0)
> 				continue;
> 			for(j = 0;j < n;j ++)
> 				less += image[i][j];
> 			if(less == 0)
> 			{
> 				leastnum ++;
> 				least = i;
> 			}
> 		}
> 	}
> 	if(leastnum == 0 && finish == n) // all characters sorted
> 		return 1;
> 	if(leastnum == 0)
> 		return -1;
> 	return 0;
> }
> 
> int main()
> {
> 	int i, j;
> 	char left, right;
> 	bool ic, dt;
> 	int icnum, dtnum;
> 	int ham;
> 	cin>>n>>m;
> 	while(n + m)
> 	{
> 		// initialization
> 		ic = dt = 0;
> 		for(i = 0;i < n;i ++)
> 		{
> 			for(j = 0;j < n;j ++)
> 				matrix[i][j] = 0;
> 		}
> 		// input the relations and process
> 		for(i = 0;i < m;i ++)
> 		{
> 			cin>>left;
> 			cin>>right;
> 			cin>>right;
> 			if(ic || dt)
> 				continue;
> 			matrix[right - 'A'][left - 'A'] = 1;
> 			ham = hamilton(); // check weather there is a hamilton track existing
> 			if(ham == 1)
> 			{
> 				dt = 1;
> 				dtnum = i + 1;
> 			}
> 			if(ham == -1)
> 			{
> 				ic = 1;
> 				icnum = i + 1;
> 			}
> 		}
> 		if(ic)
> 			cout<<"Inconsistency found after "<<icnum<<" relations."<<endl;
> 		else
> 		{
> 			if(dt)
> 			{
> 				cout<<"Sorted sequence determined after "<<dtnum<<" relations: ";
> 				for(i = 0;i < n;i ++)
> 					cout<<char('A' + seq[i]);
> 				cout<<'.'<<endl;
> 			}
> 			else
> 				cout<<"Sorted sequence cannot be determined."<<endl;
> 		}
> 		cin>>n>>m;
> 	}
> 	return 0;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator