首页 > 代码库 > poj 1094
poj 1094
唉 这几天有点热 有点烦躁 以后能做成什么样。。。。
题意:给定n个字母《0+A,...n+A》 和m个关系 想x>y 问是否能唯一确定他们的大小关系
1 在第几个关系能确定他们的排序 就输出这个位置和排序
2 如果出现矛盾就输出矛盾的位置
3 整个关系输入之后还不能确定则输出不能确定关系
?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | #include<iostream> #include<cstring> using namespace std; int map[55][55]; int in[55]; int jie[55]; int n; int sort() //1 不能排序 ; 2 能排序 { int ji[55]; int f=2; // memset(s,0,sizeof(s)); int i,j; int x,sum; for (i=1;i<=n;i++) ji[i]=in[i]; for (i=1;i<=n;i++) { sum=0; for (j=1;j<=n;j++) if (ji[j]==0) { sum++; x=j; } if (sum==0) return 1; //是否有环 if (sum>1) f=0; jie[i]=x; ji[x]=-1; for (j=1;j<=n;j++) if (map[x][j]) ji[j]--; } return f; } int main() { int yes,i; char s[11]; int m; while (cin>>n>>m) { yes=0; if (n==0&&m==0) break ; memset (in,0, sizeof (in)); memset (map,0, sizeof (map)); for (i=1;i<=m;i++) { cin>>s; if (yes) continue ; int u=s[0]- ‘A‘ +1; int v=s[2]- ‘A‘ +1; if (s[1]== ‘<‘ ) { if (map[v][u]) { cout<< "Inconsistency found after " <<i<< " relations." <<endl; yes=1; continue ; } map[u][v]=1; in[v]++; } else { if (map[u][v]) { cout<< "Inconsistency found after " <<i<< " relations." <<endl; yes=1; continue ; } map[v][u]=1; in[u]++; } int x=sort(); if (x==1) { cout<< "Inconsistency found after " <<i<< " relations." <<endl; yes=1; continue ; } if (x==2) { cout<< "Sorted sequence determined after " <<i<< " relations: " ; for ( int j=1;j<=n;j++) cout<<( char )(jie[j]-1+ ‘A‘ ); cout<< ‘.‘ <<endl; yes=1; } } if (!yes) cout<< "Sorted sequence cannot be determined." <<endl; } return 0; } |
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。