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

1094求助

Posted by zouyuanrenren at 2006-04-13 21:53:39 on Problem 1094 
感觉算法没有问题
依次读入关系，在邻接矩阵中加入边，按出度进行拓扑排序
找到出度为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