题目背景
土豪大学的计算机系开了一门数字逻辑电路课，第一个实验叫做“点亮数字人生”，要用最基础的逻辑元件组装出实际可用的电路。时间已经是深夜了，尽管实验箱上密密麻麻的连线已经拆装了好几遍，小君同学却依旧没能让她的电路正常工作。你能帮助她模拟出电路的功能，成功点亮她的数字人生吗？
问题描述
本题中，你需要实现一个简单的数字逻辑电路模拟器。如果你已经有了此方面的基础，可以直接跳过本节。在阅读时，也可以参照前两个样例的图示和解释，这有助于你更好地理解数字逻辑电路的工作原理。
数字逻辑电路是用来传输数字信号（也就是二进制信号）的电路。一般来说，数字逻辑电路可以分为两大类，即组合逻辑（combinational logic）电路和时序逻辑（sequential logic）电路。在本题中，我们仅关注组合逻辑电路。这种电路仅由逻辑门（logical gate）构成。一个逻辑门可以理解为一个多输入单输出的函数，输入端连接至少一个信号，而后经过一定的逻辑运算输出一个信号。常见的逻辑门包括与（AND）、或（OR）、非（NOT）、异或（XOR）等，均与编程语言中的按位运算是对应的。
将一系列的逻辑门连接起来，就能构成具有特定功能的电路。它的功能可能很简单（如一位二进制加法只需要一个异或门），也可能极其复杂（如除法）。无论复杂程度，这类电路的特点是：它不维持任何的状态，任何时刻输出只与输入有关，随输入变化。真实世界中的逻辑器件由于物理规律的限制，存在信号传播延时。为了简单起见，本题中我们模拟的组合逻辑电路不考虑延时：一旦输入变化，输出立刻跟着变化。
考虑到组合逻辑电路的这一特性，设计时不能允许组合环路（combinational loop）的存在，即某逻辑门的输入经过了一系列器件之后又被连接到了自己的输入端。真实世界中，这种做法将导致电路变得不稳定，甚至损坏元器件。因此，你也需要探测可能的环路。需要注意，环路的存在性与逻辑门的具体功能没有任何关系；只要连接关系上存在环路，电路就无法正常工作。
输入格式
输入数据包括若干个独立的问题，第一行一个整数 Q，满足 1≤Q≤Qmax。接下来依次是这 Q 个问题的输入，你需要对每个问题进行处理，并且按照顺序输出对应的答案。
每一个问题的输入在逻辑上可分为两部分。第一部分定义了整个电路的结构，第二部分定义了输入和输出的要求。实际上两部分之间没有分隔，顺序读入即可。
第一部分
第一行是两个空格分隔的整数 M,N，分别表示了整个电路的输入和器件的数量，满足 1≤N≤Nmax 并且 0≤M≤kmaxN。其中 kmax 和 Nmax 都是与测试点编号有关的参数。
接下来 N 行，每行描述一个器件，编号从 1 开始递增，格式如下：
FUNC k L_1 L_2 ... L_k None
其中 FUNC 代表具体的逻辑功能，k 表示输入的数量，后面跟着该器件的 k 个输入端描述 L，格式是以下二者之一：
Im：表示第 m 个输入信号连接到此输入端，保证 1≤m≤M；On：表示第 n 个器件的输出连接到此输入端，保证 1≤n≤N。所有可能的 FUNC 和允许的输入端数量如下表所述：
FUNC最少输入数量最多输入数量功能描述NOT11非AND2kmax与OR2kmax或XOR2kmax异或NAND2kmax与非（先全部与后取非）NOR2kmax或非（先全部或后取非）所有的器件均只有一个输出，但这个输出信号可以被用作多个器件的输入。
第二部分
第一行是一个整数 S，表示此电路需要运行 S 次。每次运行，都会给定一组输入，并检查部分器件的输出是否正确。S 满足 1≤S≤Smax，其中 Smax 是一个与测试点编号有关的参数。
接下来的 S 行为输入描述，每一行的格式如下：
I_1 I_2 ... I_M
None
每行有 M 个可能为 0 或 1 的数字，表示各个输入信号（按编号排列）的状态。
接下来的 S 行为输出描述，每一行的格式如下：
s_i O_1 O_2 ... O_s
None
第一个整数 1≤si≤N(1≤i≤S) 表示需要输出的信号数量。后面共有 si 个在 1 到 N 之间的数字，表示在对应的输入下，组合逻辑完成计算后，需要输出结果的器件编号。
注意 O 序列不一定是递增的，即要求输出的器件可能以任意顺序出现。
输出格式
对于输入中的 Q 个问题，你需要按照输入顺序输出每一个问题的答案：
如果你检测到电路中存在组合环路，则请输出一行，内容是 LOOP，无需输出其他任何内容。
如果电路可以正常工作，则请输出 S 行，每一行包含 si 个用空格分隔的数字（可能为 0 或 1），依次表示“输出描述”中要求的各个器件的运算结果。
样例输入1
1
3 5
XOR 2 I1 I2
XOR 2 O1 I3
AND 2 O1 I3
AND 2 I1 I2
OR 2 O3 O4
4
0 1 1
1 0 1
1 1 1
0 0 0
2 5 2
2 5 2
2 5 2
2 5 2
Data
样例输出1
1 0
1 0
1 1
0 0
Data
样例1说明
本样例只有一个问题，它定义的组合逻辑电路结构如下图所示。其功能是一位全加器，即将三个信号相加，得到一个两位二进制数。要求的器件 2 的输出是向更高位的进位信号，器件 5 的输出是本位的求和信号。
正在上传…重新上传取消
对于第一组输入 0 1 1，输出是 1 0；对于第二组输入 1 0 1，输出恰好依旧是 1 0（但电路内部状态不同）。
样例输入2
1
2 6
NOR 2 O4 I2
AND 2 O4 O6
XOR 2 O5 O1
NOT 1 O6
NAND 2 O2 O2
AND 2 I1 O3
2
0 0
1 0
3 2 3 4
6 1 2 3 4 5 6
Data
样例输出2
LOOP
Data
样例2说明
本样例也只有一个问题，它定义的组合逻辑电路结构如下图所示。
正在上传…重新上传取消
这是一个带组合环路的电路，因此无法正常工作。特别地，其中最短的环路有以下三条：
6 - 2 - 5 - 3 - 64 - 1 - 3 - 6 - 42 - 5 - 3 - 6 - 2
评测用例规模与约定
本题共有 10 个测试点，每个测试点占 10 分。
正在上传…重新上传取消
#include<iostream>
#include<queue>
using namespace std;
enum Etype{IN,NOT,AND,OR,XOR,NAND,NOR};//枚举元件类型，IN为输入
const int Nmax=3005;//设置包括输入点的最大元件数量
int d[1000];//拓扑排序时记录结点的前置结点数（入度）
int inp[3000][10000];//记录输入
//定义元件结构体
typedef struct {
Etype tp;//元件类型
int val;//元件输出值，未被搜索到时记为-1
int innum;//该元件的输入个数
int input[6];//该元件的输入源
Eelem(){
this->innum=0;
this->tp=IN;
this->val=-1;
for(int i=0;i<6;i++){
this->input[i]=-1;
}
}
}Eelem;
Eelem Eroad[Nmax];//整体电路
int output(int i);
//结点为NOT元件时求其输出；
int NOTout(int i){
if(Eroad[i].val==-1){
Eroad[i].val=!output(Eroad[i].input[0]);
}
return Eroad[i].val;
}
//结点为AND元件时求其输出；
int ANDout(int i){
int c=1;
if(Eroad[i].val==-1){
for(int j=0;j<Eroad[i].innum;j++){
c=c&output(Eroad[i].input[j]);
}
Eroad[i].val=c;
}
return Eroad[i].val;
}
//结点为OR元件时求其输出；
int ORout(int i){
int c=0;
if(Eroad[i].val==-1){
for(int j=0;j<Eroad[i].innum;j++){
c=c|output(Eroad[i].input[j]);
}
Eroad[i].val=c;
}
return Eroad[i].val;
}
//结点为XOR元件时求其输出；
int XORout(int i){
if(Eroad[i].val==-1){
int c=output(Eroad[i].input[0]);
for(int j=1;j<Eroad[i].innum;j++){
c=c^output(Eroad[i].input[j]);
}
Eroad[i].val=c;
}
return Eroad[i].val;
}
//结点为NAND元件时求其输出；
int NANDout(int i){
int c=1;
if(Eroad[i].val==-1){
for(int j=0;j<Eroad[i].innum;j++){
c=c&output(Eroad[i].input[j]);
}
Eroad[i].val=!c;
}
return Eroad[i].val;
}
//结点为NOR元件时求其输出；
int NORout(int i){
int c=0;
if(Eroad[i].val==-1){
for(int j=0;j<Eroad[i].innum;j++){
c=c|output(Eroad[i].input[j]);
}
Eroad[i].val=!c;
}
return Eroad[i].val;
}
//对标号为i的结点求其输出
int output(int i){
if(Eroad[i].tp==IN){
return Eroad[i].val;
}else if(Eroad[i].tp==NOT){
return NOTout(i);
}else if(Eroad[i].tp==AND){
return ANDout(i);
}else if(Eroad[i].tp==OR){
return ORout(i);
}else if(Eroad[i].tp==XOR){
return XORout(i);
}else if(Eroad[i].tp==NAND){
return NANDout(i);
}else if(Eroad[i].tp==NOR){
return NORout(i);
}else{
return -1;
}
}
//设定j号元件（非输入点）的类型
int setelemtype(string s,int M,int j){
if(s=="NOT"){
Eroad[M+j].tp=NOT;
}else if(s=="AND"){
Eroad[M+j].tp=AND;
}else if(s=="OR"){
Eroad[M+j].tp=OR;
}else if(s=="XOR"){
Eroad[M+j].tp=XOR;
}else if(s=="NAND"){
Eroad[M+j].tp=NAND;
}else if(s=="NOR"){
Eroad[M+j].tp=NOR;
}else{
return -1;
}
}
//使用拓扑排序算法判断是否有环存在；
bool IsCircle(int M,int N){
queue<int> q;
bool ans=false;
for(int i=0;i<N ;i++){
if(d[i]==0)q.push(i);
}
while(!q.empty()){
int v = q.front();
q.pop();
for(int i=0;i<Eroad[M+v].innum;i++){
if(Eroad[M+v].input[i]>=M){
d[Eroad[M+v].input[i]-M]--;
if(!d[Eroad[M+v].input[i]-M])q.push(Eroad[M+v].input[i]-M);
}
}
}
for(int i=0;i<N;i++){
if(d[i]!=0)ans=true;
}
return ans;
}
int main(){
int Q,M,N,k,S,front,si,ans;
string et;
char sym;
cin>>Q;
for(int i=0;i<Q;i++){
cin>>M>>N;
//设定M个输入点
for(int j=0;j<M;j++){
Eroad[j].tp=IN;
Eroad[j].val=-1;
}
//初始化拓扑排序所用入度数组
for(int j=0;j<1000;j++){
d[j]=0;
}
//设置各个元件
for(int j=0;j<N;j++){
Eroad[M+j].val=-1;
cin>>et;
setelemtype(et,M,j);//设置元件类型
cin>>k;
Eroad[M+j].innum=k;//设置元件输入数量
for(int c=0;c<k;c++){
getchar();
sym=getchar();
cin>>front;
if(sym=='I'){
Eroad[M+j].input[c]=front-1;//输入源为输入点
}else{
Eroad[M+j].input[c]=front+M-1;//输入源为其他元件
d[front-1]+=1;//此时将输入源对应元件的入度加1
}
}
}
//读取运行次数
cin>>S;
//记录各次输入
for(int j=0;j<S;j++){
for(int c=0;c<M;c++){
cin>>inp[c][j];
}
}
//判断是否有环
if(IsCircle(M,N)){//有环，读取剩余输入，输出LOOP；
for(int j=0;j<S;j++){
cin>>si;
for(int c=0;c<si;c++){
cin>>front;
}
}
cout<<"LOOP"<<endl;
}else{//无环
for(int j=0;j<S;j++){
cin>>si;
for(int c=0;c<M;c++){//将输入值写入相应输入点
Eroad[c].val=inp[c][j];
}
for(int c=M;c<M+N;c++){//初始化各元件输出值
Eroad[c].val=-1;
}
for(int c=0;c<si;c++){//输出结果
cin>>front;
cout<<output(M+front-1)<<" ";
}
cout<<endl;
}
}
}
return 0;
}
这题主要有三点，一、以适合的结构存储元件，二、BFS得出各元件输出，同时设置记忆提高效率，三、拓扑排序判断环路。代码的可读性应该还算不错，细节可以读一下代码
