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

Re:分享两组关键性数据:

Posted by jj4545 at 2020-10-14 16:58:25 on Problem 1094
In Reply To:分享两组关键性数据: Posted by:MyTalent at 2013-05-08 23:24:07
> 6 6
> A<F
> B<D
> C<E
> F<D
> D<E
> E<F
> output:
> Inconsistency found after 6 relations.
> 
> 5 5
> A<B
> B<C
> C<D
> D<E
> E<A
> output:
> Sorted sequence determined after 4 relations: ABCDE
> 
> 第一个例子讲述的是:矛盾和多选,优先判断是否矛盾
> 第二个例子讲述的是:在矛盾之前如果有成功的,算是成功
> 
> 我的代码比较笨,解决第一个用例用的是进行二次测试的办法:
> #include <cstdio>
> #include <cstring>
> #define rep(i,repstt,repend) for(int i=repstt;i<repend;i++)
> #define INIT(a,b) memset(a,b,sizeof(a))
> int into[30],ans[30],n,m;
> char tmpa,tmpb;
> bool f[30][30];
> int topo_sort(int sz,int work){
> 	INIT(into,0);
> 	rep(i,0,sz)rep(j,0,sz)
> 		if(f[i][j])
> 			into[j]++;
> 	rep(i,0,sz){
> 		int head,ok=0;
> 		rep(j,0,sz)
> 		if(!into[j]){
> 			head=j;
> 			ok++;
> 		}
> 		if(!ok)
> 			return 0;
> 		if(work==1&&ok>1)
> 			return -1;
> 		rep(k,0,sz)
> 			if(f[head][k])
> 				into[k]--;
> 		ans[i]=head;
> 		into[head]=-1;
> 	}
> 	return 1;
> }
> int main(){
> 	int res,i;
> 	while(scanf("%d%d",&n,&m)&&(n+m)){
> 		bool ud=1;
> 		INIT(f,0);
> 		for(i=0;i<m;i++){
> 			scanf(" %c %*c %c",&tmpa,&tmpb);
> 			f[tmpa-'A'][tmpb-'A']=1;
> 			res=topo_sort(n,0);
> 			if(res)//二次测试
> 				res=topo_sort(n,1);
> 			if(res==1){
> 				printf("Sorted sequence determined after %d relations: ",i+1);
> 				rep(j,0,n)putchar(ans[j]+'A');
> 				printf(".\n");
> 				rep(j,i+1,m)scanf(" %*c %*c %*c");
> 				ud=0;
> 				break;
> 			}else if(!res){
> 				printf("Inconsistency found after %d relations.\n",i+1);
> 				rep(j,i+1,m)scanf(" %*c %*c %*c");
> 				ud=0;
> 				break;
> 			}
> 		}
> 		if(ud)printf("Sorted sequence cannot be determined.\n");
> 	}
> }

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