题意：n个人排名（0~n-1），m条信息，信息有三种：“a<b”，“a>b”，“a=b”（按照RP排序，编号越大RP越高）。要求判断是否可以建立排行榜。输入有多组，输出三种格式，如果信息冲突“CONFLICT”，如果信息不完全“UNCERTAIN”，如果没问题“OK”。
输入样例：
3 3 0 > 1 1 < 2 0 > 2 4 4 1 = 2 1 > 3 2 > 0 0 > 1 3 3 1 > 0 1 > 2 2 < 1
输出样例：
OK
CONFLICT
UNCERTAIN
做题思路：
“=”用并查集合并节点，然后拓扑各集合
合并后集合数目需要，m条信息除去“=”的。父节点需要（f），用于查集合的标志节点。入度需要（son），用于找入度为0的集合。
外援解释：“
- 信息不完全, 意味着拓扑中同时出现了多个可拓扑的节点(删入弧后入度同时为0). 根据拓扑排序的原理, 这时的顺序可以随便取, 对本题来讲就是信息不完全了.
- 信息冲突, 意味着出现了反层次的边, 最终结果是形成环. 根据拓扑排序的原理, 有环图最终会剩余至少一个节点未能进行拓扑.
- 对图形进行拓扑排序. 可能出现如下三种情况:
- 若最终拓扑节点数小于人员总数, 则一定是出现了信息冲突
- 若拓扑途中出现了多个可拓扑的节点, 则是出现了信息不完全
- 没有以上两点, 则排名唯一确定
”
理解：
如果入读为0的点集有多个，就是信息不完全，因为这些点没有顺序编排。
如果形成环，拓扑便利时（根据入读为0的点）没办法全部找到点集就是信息冲突。
代码如下：
#include <iostream> #include <cstring> #include <vector> #include <queue> using namespace std; const int N = 10001; char o[2 * N]; int n, m, f[N], son[N], rank1[N], xx[2 * N], yy[2 * N];//n个人，m条信息，入度是son，父节点是f，信息格式“xx o yy” vector<int>g[N];//图的存法 void initset(int n) { for (int i = 0; i <= n; i++) { f[i] = i; rank1[i] = 0; g[i].clear(); } memset(son, 0, sizeof(son)); } //缩点 int find(int x) { int i, j = x; while (j != f[j])j = f[j]; while (j != x) { i = f[x]; f[x] = j; x = i; } return j; } //合并成点集 bool Union(int x , int y) { int a = find(x), b = find(y); if (a == b) { f[a] = b; return false; } if (a > b) { f[b] = a; } else { f[a] = b; } return true; } /* bool Union(int x, int y) {//看不懂rank是什么原理所以换了一下，竟然通过了 int a = find(x), b = find(y); if (a == b) { return false; } if (rank1[a] > rank1[b]) { f[b] = a; } else { if (rank1[a] == rank1[b]) { rank1[b]++; } f[a] = b; } return true; } */ int main() { int u, v; char ch; while (cin >> n >> m) { initset(n); int num = n; for (int i = 0; i < m; i++) { cin >> xx[i] >> o[i] >> yy[i]; if (o[i] == '=') { if (Union(xx[i], yy[i])) num--; } } for (int i = 0; i < m; i++) { if (o[i] != '=') { int x = find(xx[i]), y = find(yy[i]); if (o[i] == '>') { g[x].push_back(y); son[y]++; } else { g[y].push_back(x); son[x]++; } } } queue<int>q; for (int i = 0; i < n; i++) { if (son[i] == 0 && i == find(i)) { q.push(i); } } int stan = 0;//是否唯一 while (!q.empty()) { if (q.size() > 1)stan = 1; int t = q.front(); q.pop(); num--; for (int v = 0; v < g[t].size(); v++) { if (--son[g[t][v]] == 0)q.push(g[t][v]); } } if (num > 0) { printf("CONFLICTn"); } else if (stan) { printf("UNCERTAINn"); } else { printf("OKn"); } } return 0; }
看着别人的写的，哈哈
QAQ
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
