社区讨论
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 条回复,欢迎继续交流。
正在加载回复...