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

狂晕啊! 一直wa,大家帮忙啦!

Posted by cugwei at 2004-06-04 12:37:58 on Problem 1094
各位大虾有谁用 拓扑 过了这题的能贴个代码或是给我发一份吗? 
我的email: cugcw@2002.cug.edu.cn 
多谢啦 

#include<iostream.h>
#include<string.h>

char letter[26];
int n,m,p,q,indeg[26],relation[26][26],tmpindeg[26],flag,out[26];

int search(char *let,char letter)//判断结点在数组中的序号
{
	int h=0;
	while(h<n&&let[h]!=letter)
		h++;
	return h;
}

/*--------拓扑排序--------*/
void topusort(int *indeg,int *t)
{
	memset(out,-1,26);
	int total,tmpadd,j,totaln=0;
	for(j=0;j<n;j++)
	{
		for(p=0;p<n;p++)
		{
			if(indeg[p]<0) continue;
			total=0;//已经决定的节点个数
			for(q=0;q<n;q++)
				if(indeg[q]==0)
				{
					total++;//入度为0的结点的个数
					tmpadd=q;//入度为0的节点位置
				}
			if(total==0)//入度为0的结点的个数为0,即图中存在环,本次排序肯定失败
			{
				flag=*t;//flag为失败时的比较次数
				break;
			}
			else if(total>1)//入度为0的结点的个数大于1,则无法判断,继续本次排序
			{
				flag=0;//flag=0表示还没有决定
				break;
			}
			else if(total==1)//入度为0的结点的个数为1,则将该结点传给 out数组
			{
				out[totaln]=tmpadd;//保存输出序列	
				totaln+=1;
				if(totaln==n)
					flag=*t;//flag为成功时的比较次数
				else flag=0;
				indeg[tmpadd]=-5;//标志该结点已经处理
				for(q=0;q<n;q++)
				{
					if(relation[q][tmpadd]==1)
						tmpindeg[q]--;//根据关系表更改入度数组
				}
			}
		}
		if(p!=n) break;
	}
}

int main()
{
	char instr[4];
	int add1,add2,totaln,i;
	cin>>n>>m;
	while(n!=0||m!=0)
	{ 
		memset(relation,0,sizeof(relation));
		memset(indeg,-1,sizeof(indeg));
		memset(letter,'0',sizeof(letter));
		totaln=0;//已经出现的结点个数	
		flag=0;
		for(i=1;i<=m;i++)
		{
			cin>>instr;
			if(flag==0)//flag=0表示还没有出错或还没有决定顺序
			{
				add1=search(letter,instr[0]);
				add2=search(letter,instr[2]);		
				if(add1==n)
				{
					add1=totaln;
					totaln++;
					indeg[add1]=0;
				}
				if(add2==n)
				{
					add2=totaln;
					totaln++;
					indeg[add2]=0;
				}//如果该结点是第一次出现		
				letter[add1]=instr[0];
				letter[add2]=instr[2];//保存结点信息
				if(relation[add2][add1]==1)	//如果这对关系已经出现过,则无需重复
					continue;
				relation[add2][add1]=1;
				indeg[add2]+=1;//添加关系及入度
				for(p=0;p<26;p++)
					tmpindeg[p]=indeg[p];//COPY一个入度数组传给拓扑排序函数			
				topusort(tmpindeg,&i);
			}
			else continue;
		}
		if(flag==0&&i==m+1)
			cout<<"Sorted sequence cannot be determined."<<endl;
		else if(p!=n&&i==m+1)
			cout<<"Inconsistency found after "<<flag<<" relations."<<endl;
		else if(p==n&&i==m+1)
		{
			cout<<"Sorted sequence determined after "<<flag<<" relations: ";
			for(i=0;i<n;i++)
				cout<<letter[out[i]];
			cout<<"."<<endl;
		}
		cin>>n>>m;
	}
}

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