90分错误在此记录
  • 板块P1347 排序
  • 楼主卷王慢即快
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/7/7 15:33
  • 上次更新2023/10/27 21:36:26
查看原帖
90分错误在此记录
494699
卷王慢即快楼主2022/7/7 15:33
#include<bits/stdc++.h> //代码可真长啊…… 
using namespace std; int n,m,h,ans=0,kt,s=0;
struct node {int x,num;}; vector<int>v[100];
int in[100],t2[100]; bool flag=false; set<int>ds;
inline void work() { int r; //定义 
	queue<int>q; int tmp[100]; memset(tmp,0,sizeof(tmp));
	for(int i=0;i<26;i++) for(int j=0;j<v[i].size();j++)
		tmp[v[i][j]]++; //初始 
	for(int i=0;i<26;i++) if(tmp[i]==0 && ds.count(i))
		cout<<char('A'+i), q.push(i);
	while(!q.empty()) {
		int nx=q.front(); q.pop();
		for(int i=0;i<v[nx].size();i++) {
			int xx=v[nx][i]; tmp[xx]--;
			if(tmp[xx]==0)//入度为 0,压入队列 
			q.push(xx),cout<<char('A'+xx);
		}
	} }
inline void com() { //与上相似 
	queue<node>q; int sum=0,tmp=0;
	for(int i=0;i<26;i++) //入度为 0
		if(in[i]==0 && ds.count(i)) q.push((node){i,1}),s++;
	while(!q.empty()) {
		node now=q.front(); q.pop();
		int nx=now.x,nn=now.num;
		for(int i=0;i<v[nx].size();i++) {
			int xx=v[nx][i]; in[xx]--;
			if(in[xx]==0) {
				q.push((node){xx,nn+1});
				s++; ans=max(ans,nn+1);
			}
		}
	} if(ans==n) {
		cout<<"Sorted sequence determined after "<<kt<<" relations:";
		work(); cout<<"."<<endl; flag=true;}
	if(s!=h) { //判断是否有环 
		cout<<"Inconsistency found after "<<kt<<" relations."<<endl;
		flag=true; }
}
int main() { cin>>n>>m;
	for(int i=1;i<=m;i++) {
		char opt,A,B; cin>>A>>opt>>B;ans=0;
		if(flag==false) {
			kt=i; v[A-'A'].push_back(B-'A');s=0;
			ds.insert(A-'A'); ds.insert(B-'A');
			h=ds.size(); t2[B-'A']++; // ∑(っ°Д°)っ咦,不见了!!
			memcpy(in,t2,sizeof(t2)); com(); //copy字符串复制函数 
		}
	} if(flag==false) cout<<"Sorted sequence cannot be determined."<<endl;
	return 0;
}
输入:

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

输出:

Sorted sequence determined after 25 relations: ACEGIKMOQSUWYZBDFHJLNPRTVX.

结果输出少了一个空格。。。

记录在此,引以为戒。

2022/7/7 15:33
加载中...