点亮数字人生( 202009-3/CCF)———附带思路和完整代码（邻接表、邻接矩阵）
文章目录
- 0 效果
- 1 题目
- 2 思路
- 3 代码
- 4 测试数据
0 效果
邻接表：
邻接矩阵：
空间复杂度：邻接表比邻接矩阵少了接近1/4的大小。
难点：图的构建、拓扑排序、计算值、逻辑运算
1 题目
2 思路
数字电路抽象出来就是有向图，中间的过程是模拟作为边的入度的点使用位计算其值作为该点的权值，最后输入的结果就是类似于计算点权重。
步骤：
- 1 构建图（邻接表、邻接矩阵），【构建的时候，就计算每个点的入度】；
- 2 存储需要测试的输入、输出数据；
- 3 使用拓扑排序来判断是否电路（有向图）是否成环；
- 4 使用类似与拓扑排序的方法来从前向后依次计算每个元器件（点）的值。
注意点：
- 每次计算下一个问题时，需要重新初始化变量；
- 每次计算时，存储原始的入度，使用临时的入度来计算（因为计算时会多次用到入度）；
- 使用
std::copy(std::begin(inDegree), std::end(inDegree), std::begin(tempInDegree));复制数组时，ccf的编译器会爆编译错误； - 计算与非（NAND）和异或时（NOR）时，非操作只最后进行一次；
- 注意换行、空格的输出；
- 下文中，输入的点的编号用0～m-1来表示，元器见点的编号用m～m+n-1来表示
以下图为例，抽象为一个有向图：
抽象后的结果：
3 代码
邻接表：
#include<cstdio>
#include<vector>
#include<string>
#include<iostream>
#include<queue>
#include<string.h>
#include<algorithm>//#include <bits/stdc++.h>
//using namespace std;const int MAXV = 510;typedef struct Node{int v;//边的终点Node(int _v):v(_v){}//初始化列表
}node;
std::vector<node> Adj[MAXV];//邻接表//int G[MAXV][MAXV] = {0};//邻接矩阵
int w[MAXV];//边权重
//bool inq[MAXV] = {false};//是否访问过
bool initV[MAXV] = {false};//是否初始化过边
int inDegree[MAXV] = {0};//入度
//int outDegree[MAXV] = {0};//出度（未使用）
std::string type[MAXV]; //器件类型
std::vector<int> testInput[10010];//测试输入
std::vector<int> testOutput[10010];//测试输出//拓扑排序，判断环
bool TopologicalSort(int n, int m){int num = 0;std::queue<int> q;int tempInDegree[MAXV];//临时存储入度memcpy(tempInDegree, inDegree, (m+n)* sizeof(int));//复制的字节数// std::copy(std::begin(inDegree), std::end(inDegree), std::begin(tempInDegree));for(int i = 0;i < n + m;i++){//将所有入度为0的顶点入队if(tempInDegree[i] == 0){q.push(i);}}while(!q.empty()){int u = q.front();q.pop();//邻接表for(int i = 0;i < Adj[u].size();i++){int v = Adj[u][i].v;tempInDegree[v]--;if(tempInDegree[v] == 0){q.push(v);}}//邻接矩阵
// for(int i = 0; i < m + n;i++){
// if(inq[i] == false && G[u][i] != 0){
// tempInDegree[i]--;
//
// if(tempInDegree[i] == 0){
// q.push(i);
// inq[i] = true;
// }
// }
// }num++;}if(num == n + m) return true;else return false;
}
//计算值
void calculateValue(int n, int m){std::queue<int> q;int tempInDegree[MAXV];//临时存储入度memcpy(tempInDegree, inDegree, (m+n)* sizeof(int));//复制的字节数for(int i = 0;i < n + m;i++){//将所有入度为0的顶点入队if(tempInDegree[i] == 0){q.push(i);}}while(!q.empty()){int u = q.front();//起始点q.pop();//邻接表for(int i = 0;i < Adj[u].size();i++){int v = Adj[u][i].v;tempInDegree[v]--;if(initV[v] == false){//之前没有被访问过w[v] = w[u];//赋予初始值if(type[v] == "NOT"){//最多或者最少都只有一个输入w[v] = (!w[v]);}initV[v] = true;}else{if(type[v] == "AND" || type[v] == "NAND"){w[v] &= w[u];}else if(type[v] == "OR" || type[v] == "NOR"){w[v] |= w[u];}else if(type[v] == "XOR"){w[v] ^= w[u];}}if(tempInDegree[v] == 0){if(type[v] == "NAND" || type[v] == "NOR"){w[v] = (!w[v]);}q.push(v);}}// for(int i = 0; i < m + n;i++){
// if(inq[i] == false && G[u][i] != 0){
// tempInDegree[i]--;
//
// if(initV[i] == false){//之前没有被访问过
// w[i] = w[u];//赋予初始值
// if(type[i] == "NOT"){//最多或者最少都只有一个输入
// w[i] = (!w[i]);
// }
// initV[i] = true;
// }else{
// if(type[i] == "AND" || type[i] == "NAND"){
// w[i] &= w[u];
// }else if(type[i] == "OR" || type[i] == "NOR"){
// w[i] |= w[u];
// }else if(type[i] == "XOR"){
// w[i] ^= w[u];
// }
// }
//
// if(tempInDegree[i] == 0){//入度为零，以它为终点的边数为0
// if(type[i] == "NAND" || type[i] == "NOR"){
// w[i] = (!w[i]);
// }
// q.push(i);
// inq[i] = true;
// }
// }
// }}}int main(){int q, m, n;scanf("%d", &q);while(q--){//问题个数//初始化for(int i = 0;i < MAXV;i++){for(std::vector<node>::iterator j = Adj[i].begin();j != Adj[i].end();){j = Adj[i].erase(j);}}//std::fill(G[0], G[0] + MAXV*MAXV, 0);memset(inDegree, 0, sizeof(inDegree));//memset(outDegree, 0, sizeof(outDegree));
// std::fill(inq, inq + MAXV, false);std::fill(initV, initV + MAXV, false);for(int i = 0;i < MAXV;i++){type[i].clear();}for(int i = 0;i < 10010;i++){for(std::vector<int>::iterator j = testInput[i].begin();j != testInput[i].end();){j = testInput[i].erase(j);}}for(int i = 0;i < 10010;i++){for(std::vector<int>::iterator j = testOutput[i].begin();j != testOutput[i].end();){j = testOutput[i].erase(j);}}scanf("%d%d", &m, &n);//输入个数，器件个数for(int num = m;num < n + m;num++){std::string FUNC;//器件描述int k;std::cin>>FUNC;type[num] = FUNC;scanf("%d", &k);for(int i = 0;i < k;i++){std::string L;std::cin>>L;int startPoint = std::atoi(L.substr(1, L.length() - 1).c_str()) - 1;//计算起始点编号if(L[0] != 'I'){//如果是输出点，则加上输入点的偏移startPoint += m;}Adj[startPoint].push_back(node(num));//构造图//G[startPoint][num] = 1;// outDegree[startPoint]++;//计算出度inDegree[num]++;//计算入度}}int s;//运算次数scanf("%d", &s);for(int i = 0;i < s;i++){//输入数据for(int j = 0;j < m;j++){int input;scanf("%d", &input);testInput[i].push_back(input);}}for(int i = 0;i < s;i++){//输出数据int OutNum;scanf("%d", &OutNum);while(OutNum--){int output;scanf("%d", &output);output = output + m - 1;testOutput[i].push_back(output);}}if(TopologicalSort(n, m) == false){//有环printf("LOOP\n");}else{//无环for(int i = 0;i < s;i++){memset(w, 0, sizeof(w));//std::fill(inq, inq + MAXV, false);std::fill(initV, initV + MAXV, false);for(int j = 0;j < testInput[i].size();j++){//给初始输入点赋值w[j] = testInput[i][j];}//计算点权calculateValue(n, m);for(int j = 0; j < testOutput[i].size();j++){if(j != 0) printf(" ");printf("%d", w[testOutput[i][j]]);}printf("\n");}}}//qreturn 0;
}- 邻接矩阵
#include<cstdio>
#include<vector>
#include<string>
#include<iostream>
#include<queue>
#include<string.h>
#include<algorithm>//#include <bits/stdc++.h>
//using namespace std;//typedef struct Node{
// int v;//边的终点
// Node(int _v):v(_v){}//初始化列表
//}node;
//std::vector<node> Adj[510];//邻接表
const int MAXV = 510;
int G[MAXV][MAXV] = {0};//邻接矩阵
int w[MAXV];//边权重
bool inq[MAXV] = {false};//是否访问过
bool initV[MAXV] = {false};//是否初始化过边
int inDegree[MAXV] = {0};//入度
int outDegree[MAXV] = {0};//出度（未使用）
std::string type[MAXV]; //器件类型
std::vector<int> testInput[10010];//测试输入
std::vector<int> testOutput[10010];//测试输出//拓扑排序，判断环
bool TopologicalSort(int n, int m){int num = 0;std::queue<int> q;int tempInDegree[MAXV];//临时存储入度memcpy(tempInDegree, inDegree, (m+n)* sizeof(int));//复制的字节数// std::copy(std::begin(inDegree), std::end(inDegree), std::begin(tempInDegree));for(int i = 0;i < n + m;i++){//将所有入度为0的顶点入队if(tempInDegree[i] == 0){q.push(i);}}while(!q.empty()){int u = q.front();q.pop();// for(int i = 0;i < Adj[u].size();i++){
// int v = Adj[u][i].v;
// inDegree[v]--;
// if(inDegree[v] == 0){
// q.push(v);
// }
// }for(int i = 0; i < m + n;i++){if(inq[i] == false && G[u][i] != 0){tempInDegree[i]--;if(tempInDegree[i] == 0){q.push(i);inq[i] = true;}}}num++;}if(num == n + m) return true;else return false;
}
//计算值
void calculateValue(int n, int m){std::queue<int> q;int tempInDegree[MAXV];//临时存储入度memcpy(tempInDegree, inDegree, (m+n)* sizeof(int));//复制的字节数for(int i = 0;i < n + m;i++){//将所有入度为0的顶点入队if(tempInDegree[i] == 0){q.push(i);}}while(!q.empty()){int u = q.front();//起始点q.pop();for(int i = 0; i < m + n;i++){if(inq[i] == false && G[u][i] != 0){tempInDegree[i]--;if(initV[i] == false){//之前没有被访问过w[i] = w[u];//赋予初始值if(type[i] == "NOT"){//最多或者最少都只有一个输入w[i] = (!w[i]);}initV[i] = true;}else{if(type[i] == "AND" || type[i] == "NAND"){w[i] &= w[u];}else if(type[i] == "OR" || type[i] == "NOR"){w[i] |= w[u];}else if(type[i] == "XOR"){w[i] ^= w[u];}}if(tempInDegree[i] == 0){//入度为零，以它为终点的边数为0if(type[i] == "NAND" || type[i] == "NOR"){w[i] = (!w[i]);}q.push(i);inq[i] = true;}}}}}int main(){int q, m, n;scanf("%d", &q);while(q--){//问题个数//初始化std::fill(G[0], G[0] + MAXV*MAXV, 0);memset(inDegree, 0, sizeof(inDegree));memset(outDegree, 0, sizeof(outDegree));std::fill(inq, inq + MAXV, false);std::fill(initV, initV + MAXV, false);for(int i = 0;i < MAXV;i++){type[i].clear();}for(int i = 0;i < 10010;i++){for(std::vector<int>::iterator j = testInput[i].begin();j != testInput[i].end();){j = testInput[i].erase(j);}}for(int i = 0;i < 10010;i++){for(std::vector<int>::iterator j = testOutput[i].begin();j != testOutput[i].end();){j = testOutput[i].erase(j);}}scanf("%d%d", &m, &n);//输入个数，器件个数for(int num = m;num < n + m;num++){std::string FUNC;//器件描述int k;std::cin>>FUNC;type[num] = FUNC;scanf("%d", &k);for(int i = 0;i < k;i++){std::string L;std::cin>>L;int startPoint = std::atoi(L.substr(1, L.length() - 1).c_str()) - 1;//计算起始点编号if(L[0] != 'I'){//如果是输出点，则加上输入点的偏移startPoint += m;}//Adj[startPoint].push_back(node(num));//构造图G[startPoint][num] = 1;outDegree[startPoint]++;//计算出度inDegree[num]++;//计算入度}}int s;scanf("%d", &s);for(int i = 0;i < s;i++){//输入数据for(int j = 0;j < m;j++){int input;scanf("%d", &input);testInput[i].push_back(input);}}for(int i = 0;i < s;i++){//输出数据int OutNum;scanf("%d", &OutNum);while(OutNum--){int output;scanf("%d", &output);output = output + m - 1;testOutput[i].push_back(output);}}if(TopologicalSort(n, m) == false){printf("LOOP\n");}else{for(int i = 0;i < s;i++){memset(w, 0, sizeof(w));std::fill(inq, inq + 510, false);std::fill(initV, initV + MAXV, false);for(int j = 0;j < testInput[i].size();j++){w[j] = testInput[i][j];}calculateValue(n, m);for(int j = 0; j < testOutput[i].size();j++){if(j != 0) printf(" ");printf("%d", w[testOutput[i][j]]);}printf("\n");}}}//qreturn 0;
}
4 测试数据
- 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输出：
1 0
1 0
1 1
0 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输出：
LOOP- 3
输入：
1
3 9
AND 3 I1 I2 I3
OR 3 I1 I2 I3
AND 2 I1 I2
AND 2 I1 I3
AND 2 I2 I3
OR 2 O1 O7
AND 2 O2 O8
NOT 1 O9
OR 3 O3 O4 O5
8
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
2 6 9
2 6 9
2 6 9
2 6 9
2 6 9
2 6 9
2 6 9
2 6 9输出：
0 0
1 0
1 0
0 1
1 0
0 1
0 1
1 1
- 4
1
3 8
NAND 2 O2 O3
NAND 2 I1 O4
NAND 2 I2 O4
NAND 2 I1 I2
NAND 2 O6 O7
NAND 2 O1 O8
NAND 2 I3 O8
NAND 2 O1 I3
8
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
1 5
1 5
1 5
1 5
1 5
1 5
1 5
1 5
输出：
0
1
1
0
1
0
0
1
- 5
输入：
1
1 2
AND 2 I1 O2
NOT 1 O1
2
0
1
0 0
2 1 2输出：
LOOP
测试数据部分参考：https://blog.csdn.net/H_X_P_/article/details/108569908