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

亲爱的同道中人进来看看!

Posted by 200609020331 at 2009-02-22 15:44:13 on Problem 1094
#include<iostream>       //POJ 1094
using namespace std;
#define SIZE 30

bool map[SIZE][SIZE],ok,in[SIZE];
int degree[SIZE];
char out[SIZE];
int stack[SIZE],f;

bool toposort(int n)
{
	ok = true;
	int c = 0,i;
	f = 0;
	int temp[SIZE];
	for(i = 1; i <= n; i++)
		temp[i] = degree[i];
	memset(in,0,sizeof(in));
	for(i = 1; i <= n; i++)
		if(!temp[i]){
			in[i] = true;
			stack[++f] = i;
		}
		while(f != 0){
			if(f > 1)
				ok = false;  //?
			int e = stack[f--];
			out[c++] = e+'A'-1;
			for(i = 1; i <= n; i++)
				if(map[e][i]){
					if(!(--temp[i])){
						in[i] = true;
						stack[++f] = i;
					}
				}
		}
		out[c] = '\0';
		if(c < n)
			return false;
		else
			return true;
}

int main()
{
	int n,k,i,p;
	char a,b,r;
	while(cin >> n >> k && n+k){
		memset(map,0,sizeof(map));
		memset(degree,0,sizeof(degree));
		bool over = false;
		bool diff = false;
		for(i = 1; i <= k; i++){
			cin >> a >> r >> b;
			map[a-'A'+1][b-'A'+1] = true;
			degree[b-'A'+1]++;
			if(!over){
				bool t =toposort(n) ;
				if(t && ok){
					over = true;
					p = i;
				}
				else if(!t){
					over = true;
					diff = true;
					p = i;
				}
			}
		}
		if(over && ok && !diff)
			cout << "Sorted sequence determined after "<<p<< " relations: "<<out<<"."<<endl;
		else if(over && diff)
			cout << "Inconsistency found after "<<p<<" relations."<<endl;
		else
			cout << "Sorted sequence cannot be determined." << endl;
	}
	return 0;
}
while(f != 0){
			if(f > 1)
				ok = false;  //这句有什么用 我一直没搞懂!如果去掉它又该怎么来写该题代码,?非常感谢你的回答!

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