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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

分享两组关键性数据:

Posted by MyTalent at 2013-05-08 23:24:07 on Problem 1094
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