Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
狂晕啊! 一直wa,大家帮忙啦!各位大虾有谁用 拓扑 过了这题的能贴个代码或是给我发一份吗? 我的email: cugcw@2002.cug.edu.cn 多谢啦 #include<iostream.h> #include<string.h> char letter[26]; int n,m,p,q,indeg[26],relation[26][26],tmpindeg[26],flag,out[26]; int search(char *let,char letter)//判断结点在数组中的序号 { int h=0; while(h<n&&let[h]!=letter) h++; return h; } /*--------拓扑排序--------*/ void topusort(int *indeg,int *t) { memset(out,-1,26); int total,tmpadd,j,totaln=0; for(j=0;j<n;j++) { for(p=0;p<n;p++) { if(indeg[p]<0) continue; total=0;//已经决定的节点个数 for(q=0;q<n;q++) if(indeg[q]==0) { total++;//入度为0的结点的个数 tmpadd=q;//入度为0的节点位置 } if(total==0)//入度为0的结点的个数为0,即图中存在环,本次排序肯定失败 { flag=*t;//flag为失败时的比较次数 break; } else if(total>1)//入度为0的结点的个数大于1,则无法判断,继续本次排序 { flag=0;//flag=0表示还没有决定 break; } else if(total==1)//入度为0的结点的个数为1,则将该结点传给 out数组 { out[totaln]=tmpadd;//保存输出序列 totaln+=1; if(totaln==n) flag=*t;//flag为成功时的比较次数 else flag=0; indeg[tmpadd]=-5;//标志该结点已经处理 for(q=0;q<n;q++) { if(relation[q][tmpadd]==1) tmpindeg[q]--;//根据关系表更改入度数组 } } } if(p!=n) break; } } int main() { char instr[4]; int add1,add2,totaln,i; cin>>n>>m; while(n!=0||m!=0) { memset(relation,0,sizeof(relation)); memset(indeg,-1,sizeof(indeg)); memset(letter,'0',sizeof(letter)); totaln=0;//已经出现的结点个数 flag=0; for(i=1;i<=m;i++) { cin>>instr; if(flag==0)//flag=0表示还没有出错或还没有决定顺序 { add1=search(letter,instr[0]); add2=search(letter,instr[2]); if(add1==n) { add1=totaln; totaln++; indeg[add1]=0; } if(add2==n) { add2=totaln; totaln++; indeg[add2]=0; }//如果该结点是第一次出现 letter[add1]=instr[0]; letter[add2]=instr[2];//保存结点信息 if(relation[add2][add1]==1) //如果这对关系已经出现过,则无需重复 continue; relation[add2][add1]=1; indeg[add2]+=1;//添加关系及入度 for(p=0;p<26;p++) tmpindeg[p]=indeg[p];//COPY一个入度数组传给拓扑排序函数 topusort(tmpindeg,&i); } else continue; } if(flag==0&&i==m+1) cout<<"Sorted sequence cannot be determined."<<endl; else if(p!=n&&i==m+1) cout<<"Inconsistency found after "<<flag<<" relations."<<endl; else if(p==n&&i==m+1) { cout<<"Sorted sequence determined after "<<flag<<" relations: "; for(i=0;i<n;i++) cout<<letter[out[i]]; cout<<"."<<endl; } cin>>n>>m; } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator