海口建站模板厂家,wordpress 音乐不中断,优化师是干嘛的,物流公司会计好做吗1 /*2 题意#xff1a;这些信息可能有三种情况#xff0c;分别是A B,A B,A B#xff0c;分别表示A的Rating高于B,等于B,小于B。3 4 现在Lele并不是让你来帮他制作这个高手榜#xff0c;他只是想知道#xff0c;根据这… 1 /*2 题意这些信息可能有三种情况分别是A B,A B,A B分别表示A的Rating高于B,等于B,小于B。3 4 现在Lele并不是让你来帮他制作这个高手榜他只是想知道根据这些信息是否能够确定出这个高手榜是的话就输出OK。5 否则就请你判断出错的原因到底是因为信息不完全输出UNCERTAIN还是因为这些信息中包含冲突输出CONFLICT。6 注意如果信息中同时包含冲突且信息不完全就输出CONFLICT。7 8 思路: 因为小于关系和大于关系可以转换一下位置 这里的问题就在与如何正确的处理相等的关系9 如果没有相等的关系一个拓扑排序算法就可以搞定了 既然元素相等那么我们取相等元素中的某一个10 数来表示每一个数不是也行吗对没错用这个数来代替所有与之相等元素的数表示 关系 也就是11 转换成集合之间的关系的处理 将每一个相等的元素集合看成一个点这个点的代表就是集合的父亲节点 12 13 那么如何来得到这个数呢并查集最适合不过了我们将相等的元素放入集合中14 当 ab时通过getFather(a) getFather(b)来处里ab的关系这里用邻接表进行处理 15 */16 #includeiostream17 #includecstring18 #includevector19 #includestack20 using namespace std;21 int f[10005];22 int rank[10005];23 int n, m;24 int getFather(int x){25 return xf[x] ? x : f[x]getFather(f[x]);26 }27 28 int Union(int a, int b){29 int fagetFather(a), fbgetFather(b);30 if(fa!fb){31 if(rank[fa]rank[fb]){32 f[fb]fa;33 rank[fa]rank[fb]1;34 }35 else{36 f[fa]fb;37 rank[fb]rank[fa]1;38 }39 return 1; 40 }41 return 0;42 }43 44 int in[10005];45 int A[10005], B[10005];46 char ch[10005]; 47 vectorintvx[10005];48 int conflict, uncertain;49 int sum;50 51 /*void topoSort(){52 for(int j1; jsum; j){53 int p0, cnt0;54 for(int i1; in; i)55 if(f[i]i in[i]0){//f[i]i表明 i是这个相等集合的代表元素也就是这个集合所有元素的父节点 56 pi;57 cnt;58 }59 if(cnt0){60 conflict1;61 return;62 }63 if(cnt1)64 uncertain1;65 int lenvx[p].size();66 for(int i0; ilen; i)67 --in[vx[p][i]];68 in[p]-1;69 }70 }*/71 72 stackintss;73 74 void topoSort(){75 for(int i1; in; i)76 if(f[i]i in[i]0)//f[i]i表明 i是这个相等集合的代表元素也就是这个集合所有元素的父节点 77 ss.push(i); 78 if(ss.size()0 sum)79 conflict1;80 while(!ss.empty()){81 int cntss.size();82 int pss.top();83 --sum;//表示剩余多少个节点没有排序 84 ss.pop();85 86 if(cnt1)87 uncertain1;88 int lenvx[p].size();89 for(int i0; ilen; i)90 if(--in[vx[p][i]]0)91 ss.push(vx[p][i]);92 if(ss.size()0 sum)93 conflict1;94 }95 } 96 97 int main(){98 while(cinnm){99 for(int i1; in; i)
100 f[i]i;
101 for(int i1; im; i){
102 scanf(%d %c %d, A[i], ch[i], B[i]);
103 A[i];
104 B[i];
105 if(ch[i])
106 Union(A[i], B[i]);
107 }
108 sum0;
109 for(int i1; in; i)
110 if(f[i]i) sum;
111 for(int i1; im; i){
112 int fagetFather(A[i]), fbgetFather(B[i]);//将每一个相等的元素集合看成一个点这个点的代表就是其父亲节点
113 if(ch[i]){
114 vx[fa].push_back(fb);
115 in[fb];
116 }
117 else if(ch[i]){
118 vx[fb].push_back(fa);
119 in[fa];
120 }
121 }
122
123 conflictuncertain0;
124 topoSort();
125 if(conflict)
126 coutCONFLICTendl;
127 else if(uncertain)
128 coutUNCERTAINendl;
129 else coutOKendl;
130 for(int i1; in; i)
131 vx[i].clear();
132
133 memset(rank, 0, sizeof(int)*(n1));
134 memset(in, 0, sizeof(int)*(n1));
135 while(!ss.empty())
136 ss.pop();
137 }
138 } 转载于:https://www.cnblogs.com/hujunzheng/p/3901530.html
