社区讨论

90分错误在此记录

P1347[ECNA 2001] 排序参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo8npsun
此快照首次捕获于
2023/10/27 21:36
2 年前
此快照最后确认于
2023/10/27 21:36
2 年前
查看原帖
CPP
#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;
}
CPP
输入:

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

CPP
输出:

Sorted sequence determined after 25 relations: ACEGIKMOQSUWYZBDFHJLNPRTVX.

结果输出少了一个空格。。。
记录在此,引以为戒。

回复

2 条回复,欢迎继续交流。

正在加载回复...