90pts求调
  • 板块P1347 排序
  • 楼主TuMi_Yang
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/13 17:07
  • 上次更新2024/10/13 19:20:47
查看原帖
90pts求调
1120425
TuMi_Yang楼主2024/10/13 17:07

试了一下,开O2就过不了,但是不开就AC了

#include<bits/stdc++.h>
using namespace std;
vector<int>mapp[650];

int n,m,flag=-1,k=0;
int in[650];
int in1[650];
int bo[650];
bool cir;
int kkk=0;
void sort_topo(int ppp){
	vector<char>map1;
	queue<int>q;
	int cnt;
	for(int i=1;i<=n;i++){
		if(in1[i]==0&&bo[i]){
			q.push(i);
			cnt++;
			if(cnt>1)flag=2;
		}
		//TODO
	}
	while(!q.empty()){
		int topo1=q.front();
		int sizen=mapp[topo1].size();
		map1.push_back(topo1-1+'A');
//		printf("%d ",topo1);
		cnt=0;
		q.pop();
		for(int i=0;i<sizen;i++){
			in1[mapp[topo1][i]]--;
			if(in1[mapp[topo1][i]]==0){
				q.push(mapp[topo1][i]);
				cnt++;
			}
			//TODO
		}
		if(cnt>1)flag=2;
		//TODO
	}
//	printf("size:%d\n",map1.size());
	if(map1.size()<kkk){
		flag=0;
		return ;
	}
	if(map1.size()==n&&flag!=2){
		flag=1;
		printf("Sorted sequence determined after %d relations: ",ppp);
		int sz=map1.size();
		for(int i=0;i<map1.size();i++){
			cout<<map1[i];
		}
		printf(".");
		return ;
	}
	return ;
}
int main(){
//	printf("%d %d\n",'A','B');
	scanf("%d%d",&n,&m);
	memset(bo,0,sizeof(bo));
	for(int i=1;i<=m;i++){
		string a;
		cin>>a;
		int x=a[0]+1-'A';
		if(!bo[x]){
			bo[x]=1;
			kkk++;
		}
		int y=a[2]+1-'A';
		if(!bo[y]){
			bo[y]=1;
			kkk++;
		}
//		printf("%d %d\n",x,y);
		mapp[x].push_back(y);
		in[y]++;
		flag=-1;
		for(int j=1;j<=26;j++)in1[j]=in[j];
		sort_topo(i);
		if(flag==1){
			return 0;
		}
		if(flag==0){
			printf("Inconsistency found after %d relations.",i);
			return 0;
		}
	}
	printf("Sorted sequence cannot be determined.");
//	sort_topo();
	return 0;
	
}

第一个和第九个过不了

26 26
A<B
B<C
C<D
D<E
E<F
F<G
G<H
H<I
I<J
J<K
K<L
L<M
M<N
N<O
O<P
P<Q
Q<R
R<S
S<T
T<U
U<V
V<W
W<X
X<Y
Y<Z
Z<A

第一个输入

Sorted sequence determined after 25 relations: ABCDEFGHIJKLMNOPQRSTUVWXYZ.

第一个输出

2024/10/13 17:07
加载中...