P1347 排序
2023-04-18 16:43:25 时间
题目描述
一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列,例如,一个有序的数列 A,B,C,D 表示A<B,B<C,C<D。在这道题中,我们将给你一系列形如 A<B 的关系,并要求你判断是否能够根据这些关系确定这个数列的顺序。
输入格式
第一行有两个正整数 n,m,n 表示需要排序的元素数量,2≤n≤26,第 1 到 n 个元素将用大写的 A,B,C,D… 表示。m 表示将给出的形如A<B 的关系的数量。
接下来有 m 行,每行有 3 个字符,分别为一个大写字母,一个 <
符号,一个大写字母,表示两个元素之间的关系。
输出格式
若根据前 xx 个关系即可确定这 nn 个元素的顺序 yyy..y
(如 ABC
),输出
Sorted sequence determined after xxx relations: yyy...y.
若根据前 xx 个关系即发现存在矛盾(如A<B,B<C,C<A),输出
Inconsistency found after x relations.
若根据这 m 个关系无法确定这 n 个元素的顺序,输出
Sorted sequence cannot be determined.
(提示:确定 nn 个元素的顺序后即可结束程序,可以不用考虑确定顺序之后出现矛盾的情况)
输入输出样例
输入 #1复制
4 6 A<B A<C B<C C<D B<D A<B
输出 #1复制
Sorted sequence determined after 4 relations: ABCD.
解析:
这道题第一眼想到的就是先后顺序,这是可以想到拓扑排序。
注意:char(i+"A") != A这是我在测试是总过不了的。字符串和字符要分辨
#include<bits/stdc++.h>
using namespace std;
const int N = 50;
struct Node {
int u;
int val;
Node(int u = 0,int val = 0):u(u),val(val){}
};
vector<int> vec[N];
int in[N];
set<int> s1;
int in1[N];
int n, m,k,have,sum,ans;
vector<char> vv;
void topu() {
vv.clear();
queue<Node> q;
for (int i = 0; i < 26; i++) {
if (in1[i] == 0 && s1.count(i)) {
q.push(Node(i, 1));
sum++;
vv.push_back(char(i + 'A'));
}
}
while (!q.empty()) {
int u = q.front().u;
int val = q.front().val;
q.pop();
for (int i = 0; i < vec[u].size(); i++) {
int v = vec[u][i];
in1[v]--;
if (in1[v] == 0) {
sum++;
q.push(Node(v, val + 1));
ans = max(ans, val + 1);
vv.push_back(char(v + 'A'));
}
}
}
if (ans == n) {
printf("Sorted sequence determined after %d relations: ", k);
for (int i = 0; i < vv.size(); i++) {
cout << vv[i];
}
cout << ".";
exit(0);
}
else if(sum != have) {
printf("Inconsistency found after %d relations.", k);
exit(0);
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
string s;
cin >> s;
k = i;
vec[s[0] - 'A'].push_back(s[2] - 'A');
s1.insert(s[0] - 'A');
s1.insert(s[2] - 'A');
have = s1.size();
in[s[2] - 'A']++;
sum = 0;
ans = 0;
memcpy(in1, in, sizeof(in));
topu();
}
printf("Sorted sequence cannot be determined.");
return 0;
}
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击