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

说下一点思路,仅供参考,Floyd+Toppsort(附代码)

Posted by mengfanqi at 2010-09-04 10:40:21 on Problem 1094
思路:
1.读入一条边后,先做Floyd,确认是否有环,若有环退出,输出"Inconsistency",矛盾
2.再做Toposort,判断已读入的几条边是否可以满足输出,在进行拓扑排序时,观察出度为0的点有多少,
若有大于两个以上的点,则退出,不考虑,继续读入边,若恰好有一个点,则继续拓扑排序,直到最后
n个点都排好序,则输出"Sorted sequence determined",若有0个点,则有环(这条可以省略,因为前面的Floyd
已经确认了没有环)
3.最后加入了m条边还是没有确定下来,则输出"Sorted sequence cannot be determined"
#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
#include<string.h>
#define INF 2000
int flag;
int maze[30][30];
char str[1000][5];
int ans[30];

void Floyd(int n)
{
	int i,j,k;
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			for(k=0;k<n;k++){
				if(!maze[j][k] && maze[j][i] && maze[i][k])
					maze[j][k]=1;
			}
		}
	}
	for(i=0;i<n;i++){
		if(maze[i][i]){
			flag=1;
		}	
	}
}
int Toposort(int n)
{
	int out[30];  //出度表
	int visited[30]; //访问表
	memset(out,0,sizeof(out));
	memset(ans,0,sizeof(ans));
	memset(visited,0,sizeof(visited));
	int i,j,k;
	for(i=0;i<n;i++){  //初始化出度表
		for(j=0;j<n;j++){
			if(maze[i][j])
				out[j]++;
		}
	}
	int count,pos=0;
	for(i=0;i<n;i++){
		count=0;
		for(j=0;j<n;j++){
			if(out[j]==0 && !visited[j]){
				count++;
				pos=j;
			}
		}
		if(count>1) return 0; 
		else if(count==0) {
			flag=1;
			return 1;//有环	
		}
		ans[i]=pos;
		visited[pos]=1;
		for(j=0;j<n;j++){
			if(maze[pos][j])
				out[j]--;
		}
	}
	flag=2;
	return 2;  //得到结果
}
int main()
{
	int n,m,i,j,k,x,y;
	while(scanf("%d%d",&n,&m)!=EOF){
		if(n==0 && m==0) break;
		memset(maze,0,sizeof(maze));
		flag=0;
		for(i=0;i<m;i++){         //输入
			scanf("%s",str[i]);
		}
		for(i=0;i<m;i++){      //一步一步的检查
			x=str[i][0]-'A'; y=str[i][2]-'A';
			maze[x][y]=1;
			Floyd(n);          //检查是否有环并更新maze
			if(flag) break;              
			if(Toposort(n)) //检查是否有多条路径 和是否能输出
				break;
		}
		if(i==m){
			printf("Sorted sequence cannot be determined.\n");
		}
		if(flag==1){
			printf("Inconsistency found after %d relations.\n",i+1);
		}else if(flag==2){
			printf("Sorted sequence determined after %d relations: ",i+1);
			for(i=0;i<n;i++){
				printf("%c",ans[i]+'A');
			}
			printf(".\n");
		}

	}
	system("pause");
	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