`
dato0123
  • 浏览: 906648 次
文章分类
社区版块
存档分类
最新评论

POJ 1094解题报告

 
阅读更多

POJ 1094解题报告

这个题主要的是使用拓扑排序,相关算法随便找一本算法的书都能看到,也不难,就不罗嗦了。

我使用邻接表来保存图,并使用dm,dn分别保存每个节点(即字母)的出度和入度。

我只想强调一下需要注意的:

一、先判断是否有环路

我就是一开始在检测到不能确定序列的时候就直接返回了,而没有判断是否有环路,结果一直WA;

二、当序列可以确定或是检测到环路的时候,忽略后边的输入。

Code:
  1. #include<iostream>
  2. #include<fstream>
  3. usingnamespacestd;
  4. charG[26][26];
  5. intdm[26];//每一列的和,即每个字母的入度
  6. intdn[26];//每一行的和,即每个字母的出度
  7. intm,n;
  8. charresult[27];
  9. intTopoSort()
  10. {
  11. intindex;//起点
  12. intr=0;
  13. intcount;
  14. boolsorted=true;
  15. intdmt[26];
  16. intdnt[26];
  17. memcpy(dmt,dm,sizeof(dmt));
  18. memcpy(dnt,dn,sizeof(dnt));
  19. //找出入度为零的点
  20. for(intj=0;j<n;j++)
  21. {
  22. count=0;
  23. for(inti=0;i<n;i++)
  24. {
  25. if(0==dmt[i])
  26. {
  27. index=i;
  28. count++;
  29. }
  30. }
  31. if(0==count)//发现环路
  32. returncount;
  33. if(count>1)sorted=false;
  34. for(inti=0;i<dnt[index];i++)
  35. {
  36. dmt[G[index][i]-'A']--;
  37. }
  38. dmt[index]=-1;
  39. result[r++]=index+'A';
  40. }
  41. result[r]=0;
  42. if(sorted)
  43. return1;//序**定
  44. else
  45. return2;//序列不确定
  46. }
  47. intmain()
  48. {
  49. inti,j,k;
  50. charstr[4];
  51. //ifstreamin("data.in");
  52. cin>>n>>m;
  53. while(n&&m)
  54. {
  55. k=0;
  56. intfound=0;//可以完全确定序列
  57. intincons=0;//发现冲突,即环路
  58. memset(dm,0,sizeof(dm));
  59. memset(dn,0,sizeof(dn));
  60. memset(G,0,sizeof(G));
  61. for(i=0;i<m;i++)
  62. {
  63. cin>>str;
  64. if(!found&&!incons)
  65. {
  66. for(j=0;j<dn[str[0]-'A'];j++)
  67. {
  68. if(G[str[0]-'A'][j]==str[2])
  69. break;
  70. }
  71. if(j==dn[str[0]-'A'])
  72. {
  73. G[str[0]-'A'][j]=str[2];
  74. dm[str[2]-'A']++;
  75. dn[str[0]-'A']++;
  76. }
  77. intres=TopoSort();
  78. if(1==res)//序列已确定
  79. {
  80. found=i+1;
  81. }
  82. elseif(0==res)//发现冲突
  83. {
  84. incons=i+1;
  85. }
  86. }
  87. }
  88. if(found)
  89. {
  90. cout<<"Sortedsequencedeterminedafter"<<found<<"relations:"<<result<<"."<<endl;
  91. }
  92. elseif(incons)
  93. {
  94. cout<<"Inconsistencyfoundafter"<<incons<<"relations."<<endl;
  95. }
  96. else
  97. {
  98. cout<<"Sortedsequencecannotbedetermined."<<endl;
  99. }
  100. cin>>n>>m;
  101. }
  102. return0;
  103. }

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics