求助
  • 板块P1347 排序
  • 楼主BiaxialRay
  • 当前回复5
  • 已保存回复5
  • 发布时间2020/8/13 17:14
  • 上次更新2023/11/6 20:24:50
查看原帖
求助
218172
BiaxialRay楼主2020/8/13 17:14
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int Maxn = 30,Maxm = 1e3;
int n,m;
int indeg[Maxn];
int indeg_[Maxn];
char result[Maxn];

int c2i(char ch){
	return ch - 'A' + 1;
}

int head[Maxn];
struct Side{
	int e;
	int next;
}side[Maxm];

void add(int start,int end,int x){
	side[x].e = end;
	side[x].next = head[start];
	head[start] = x;
	++indeg_[end];
}

int Topsort(){
	int i,flag = 0,cnt = 0,top;
	queue<int> Q;
	for(i = 1;i <= n;++i){
		indeg[i] = indeg_[i];
		if(!indeg[i]){
			Q.push(i);
			result[++cnt] = i + 'A' - 1;
			if(flag)return 0;
			flag = 1;
		}
	}
	while(!Q.empty()){
		top = Q.front();
		Q.pop();
		flag = 0;
		for(i = head[top];i;i = side[i].next){
			--indeg[side[i].e];
			if(!indeg[side[i].e]){
				Q.push(side[i].e);
				result[++cnt] = (char)(side[i].e + 'A' - 1);
				if(flag)return 0;
				flag = 1;
			}
		}
	}
	if(cnt < n)return 0;
	return 1;
}

int vis[Maxn];
int check(int x){
	int i;
	vis[x] = 1;
	for(i = head[x];i;i = side[i].next){
		if(vis[side[i].e])return 0;
		if(!check(side[i].e))return 0;
	}
	vis[x] = 0;
	return 1;
}

int main(){
	int i,j;
	char ch1,ch2,temp;
	scanf("%d%d",&n,&m);
	for(i = 1;i <= m;++i){
		memset(vis,0,sizeof(vis));
		getchar();
		scanf("%c",&ch1);
		getchar();
		scanf("%c",&ch2);
		add(c2i(ch1),c2i(ch2),i);
		if(!check(c2i(ch1))){
			printf("Inconsistency found after %d relations.",i);
			return 0;
		}
		if(Topsort()){
			printf("Sorted sequence determined after %d relations: %s",i,result+1);
			return 0;
		}
	}
	printf("Sorted sequence cannot be determined.");
	return 0;
}

只拿了20分……
第一个数据点:

4 6
C<D
C<B
B<A
C<D
D<A
A<A

输出:

Inconsistency found after 6 relations.

我在自己电脑上运行是正确的,有大佬知道为什么吗

2020/8/13 17:14
加载中...