题目来源于 https://blog.csdn.net/wingrez/article/details/88676539
背景
消息传递接口（MPI）是一个并行计算的应用程序接口，常用于超级计算机、计算机集群等环境下的程序设计。
题目
老师给了 T 份 MPI 的样例代码，每份代码都实现了 n 个进程通信。这些进程标号从 0 到 n − 1，每个进程会顺序执行自己的收发指令，如：“S x”，“R x”。“S x”表示向x 号进程发送数据，“R x”表示从 x 号进程接收数据。每一对收发命令必须匹配执行才能生效，否则会“死锁”。 举个例子，x 号进程先执行发送命令“S y”，y 号进程必. 须. 执行接送命令“R x”，这一对命令才执行成功。否则 x 号进程会一直等待 y 号进程执行对应的接收命令。反之，若 y 号进程先执行接收命令“R x”，则会一直等待 x 号进程执行发送命令“S y”，若 x号进程一直未执行发送命令“S y”，则 y 号进程会一直等待 x 号进程执行对应的发送命令。上述这样发送接收命令不匹配的情况都会造成整个程序出现“死锁”。另外，x 号进程不会执行“S x”或“R x”，即不会从自己的进程收发消息。.现在老师请你判断每份样例代码是否会出现“死锁”的情况。每个进程的指令最少有 1 条，最多有 8 条，这些指令按顺序执行，即第一条执行完毕，才能执行第二条，依次到最后一条。
输入
从标准输入读入数据。 输入第一行两个正整数 T, n，表示有 T 份样例代码，实现了 n 个进程通信。 接下来有 T × n 行，每行有若干个（1 − 8 个）字符串，相邻之间有一个空格隔开，表示相应进程的收发指令。不存在非法指令。对于第 2 + i, 0 ≤ i ≤ (T × n − 1) 行，表示第 i ÷ n（商）份代码的 i KQ/ n（余数）号进程的收发指令。 （比如，“S1”表示向 1 号进程发送消息，“R1”表示从 1 号进程接收消息。细节请参考样例。）
输出
输出到标准输出。 输出共 T 行，每行一个数字，表示对应样例代码是否出现“死锁”的情况。1 表示死锁，0 表示不死锁。
输入样例1
3 2 R1 S1 S0 R0 R1 S1 R0 S0 R1 R1 R1 R1 S1 S1 S1 S1 S0 S0 S0 S0 R0 R0 R0 R0
输出样例1
0 1 0
样例解释1
第 1 份代码中，（1）0 号进程执行的“R1”和 1 号进程执行的“S0”成功执行；（2）0 号进程执行的“S1”和 1 号进程执行的“R0”成功执行，所以未发生“死锁”，程序顺利运行。 第 2 份代码中，（1）0 号进程执行的“R1”和 1 号进程执行的“R0”一直在等待发送命令，进入“死锁”状态。 （原题中此处有错误，已更正）
输入样例2
2 3 R1 S1 R2 S0 R0 S2 S1 R1 R1 R2 S0 R0 S1 R1
输出样例2
0 1
样例解释2
第 1 份代码中，（1）2 号进程执行的“S1”和 1 号进程执行的“R2”成功执行；（2）0 号进程执行的“R1”和 1 号进程执行的“S0”成功执行；（3）0 号进程执行的“S1”和 1 号进程执行的“R0”成功执行；（4）1 号进程执行的“S2”和 2 号进程执行的“R1”成功执行；所以未发生“死锁”，程序顺利运行。 第 2 份代码中，（1）2 号进程执行的“S1”和 1 号进程执行的“R2”成功执行；（2） 0 号进程执行的“R1”和 1 号进程执行的“S0”成功执行；（3）1 号进程执行的“R0” 和 2 号进程执行的“R1”一直在等待发送命令；进入“死锁”状态。
提示
耶！第一次独立做出来第四题，不过可能也是因为这道题比较简单吧 (*^▽^*)
思路：刚开始看到这道题我的第一反应是拓扑排序，就感觉很像，但是又感觉不太对劲，去找了一圈果然没有用拓扑排序做的，然后我最后用的是暴力模拟的方法。
进行一个大循环，每次循环都遍历n个进程的列表首元素，只有当所有进程的命令列表都为空（sumarr(isempty,n)==0），或者在本次循环中各进程列表都没有改变时才跳出循环（程序中的flag）。如果遍历到的进程k为Sk或Rk，说明在从自己的进程收发消息。这种情况直接让该命令出队，flag=1如果遍历到进程k首元素是Sx，则接下来要看看进程x的首元素是否为Rk。如果是的话，这两个命令就可以抵消，两个进程队列一起出队，并置flag=1；如果进程x的首元素不是Rk，不做任何改变。到最后判断sumarr(isempty,n)==0？，如果=0，说明所有命令都被执行了，未产生死锁，输出1，否则输出0queue<com> command[MAXN]，用一个数组n个进程每个进程都有一个执行的先后顺序，先进先出，所以用queue。用队列数组来存储n个进程的待执行命令列表isempty[MAXN] 来记录第i个进程的执行命令是否为空，不空isempty[i]=1，空为0。这个数组存在的意义是因为我
#include<iostream> #include<queue> #include<cstring> using namespace std; struct com { char c; int num; com(char c,int num):c(c),num(num) {} // bool operator ==(com x)const{ // return c==x.c&&num==x.num; // } }; const int MAXN=10005; queue<com> command[MAXN]; int isempty[MAXN]; //判断该列表是否为空，不空为1，空为0 int str2int(string s) { int res=0; for(int i=0; i<s.length(); i++) { res=res*10+s[i]-'0'; } return res; } int sumarr(int a[],int n) { //求a数组的和，来判断是否所有队列全为空，即所有命令都被执行完了 int res=0; for(int i=0; i<n; i++) { res+=a[i]; } return res; } int main() { int t,n; scanf("%d%d",&t,&n); string s1,s2; getchar(); for(int i=0; i<t; i++) { memset(isempty,0,sizeof(isempty)); for(int j=0; j<n; j++) { getline(cin,s1); int index; while((index=s1.find(' '))!=string::npos) { s2=s1.substr(0,index); s1=s1.substr(index+1); command[j].push(com(s2[0],str2int(string(s2,1)))); // cout<<s2[0]<<" "<<str2int(string(s2,1))<<endl; isempty[j]=1; //不空 } command[j].push(com(s1[0],str2int(string(s1,1)))); // cout<<s1[0]<<" "<<str2int(string(s1,1))<<endl; } while(sumarr(isempty,n)!=0) { int flag=0; //如果一轮以后flag仍为0，说明这一轮没有改变 for(int k=0; k<n; k++) { if(command[k].empty()) { isempty[k]=0; continue; } com temp1=com('S',0),temp2('S',0); //这个初始化随意的，没有实际意义 temp1=command[k].front(); int from,to; //from的Sto与to的Rfrom相对应 from=k; to=temp1.num; if(from==to) { //不会从自己的进程收发消息 flag=1; command[from].pop(); continue; } // cout<<s1<<endl; if(temp1.c=='S') { //Sx // temp2=com('R',k); //Rx if(command[to].empty()) isempty[to]=0; //为空，无法取顶，这种情况下也不能匹配 else if(command[to].front().c=='R' && command[to].front().num==from) { //Sto和Rfrom可以匹配 flag=1; command[from].pop(); command[to].pop(); } } } if(flag==0) break; } if(sumarr(isempty,n)==0) { //0 不死锁 printf("0\n"); } else { printf("1\n"); } for(int k=0; k<n; k++) { while(!command[k].empty()) { command[k].pop(); } } } return 0; }
