CCCC团体程序设计天梯赛 L2

有效团队建设课程设计 #生活技巧# #团队建设技巧# #团队培训与发展#

记录天梯赛题目合集 跳转查看

题目链接

题目描述

安排宴会，将会告诉你参加宾客间的关系，询问 kk 对宾客是否可以同席。假设朋友的朋友也是朋友。但敌人的敌人并不一定就是朋友，朋友的敌人也不一定是敌人。只有单纯直接的敌对关系才是绝对不能同席的。

输入格式:
输入第一行给出33个正整数：NN（≤100），即前来参宴的宾客总人数，则这些人从11到NN编号；MM为已知两两宾客之间的关系数；KK为查询的条数。随后MM行，每行给出一对宾客之间的关系，格式为：宾客1 宾客2 关系，其中关系为1表示是朋友，-1表示是死对头。注意两个人不可能既是朋友又是敌人。最后KK行，每行给出一对需要查询的宾客编号。

输出格式:
对每个查询输出一行结果：如果两位宾客之间是朋友，且没有敌对关系，则输出No problem；如果他们之间并不是朋友，但也不敌对，则输出OK；如果他们之间有敌对，然而也有共同的朋友，则输出OK but...；如果他们之间只有敌对关系，则输出No way。

题目解析

抓住关键：只有直接敌对关系是不可同席的。那么我们就可以建立一个二维bool数组去标记哪对宾客是直接敌对关系，这对宾客就是不可同席的，具体地设 st[a][b] = 1 表示宾客a和宾客b是不可同席的。

接下来就是解决两个宾客间非敌对的具体关系，根据输出要求可以总结为：两人间是朋友，两人有共同朋友，两人间有共同敌对，两人间没有关系。考虑到我们已经特殊处理直接敌对的关系，那么我们可以将朋友关系归为一类关系网，即是朋友或共同朋友的宾客放在一个集合中，而不在同一个集合的两人就要么是直接敌对，要么有共同敌人，而直接敌对我们已经标记了，那没有标记的就是有共同敌人。

由此我们已解决该题，而处理集合关系可以使用并查集。

代码

#include <iostream>#include <algorithm>#include <cstring>#include <cmath>#include <vector>#include <queue>#include <map>#include <set>#include <unordered_map>#include <unordered_set> using namespace std; typedef long long ll;typedef pair<int, int> PII; const ll inf = 1e18;const int INF = 0x3f3f3f3f;const int N = 100 + 10; int n, m, k;bool st[N][N];int f[N]; int find(int x){if (x != f[x]) f[x] = find(f[x]);return f[x];} void solve(){cin >> n >> m >> k;for (int i = 1; i <= n; i ++) f[i] = i;while (m --) {int a, b, x;cin >> a >> b >> x;if (x == 1) {int pa = find(a), pb = find(b);if (pa == pb) continue;f[pa] = pb;}else {st[a][b] = 1;st[b][a] = 1;}}while (k --) {int a, b;cin >> a >> b;int pa = find(a), pb = find(b);if (pa == pb) {if (st[a][b]) cout << "OK but..." << '\n';else cout << "No problem" << '\n';}else {if (st[a][b]) cout << "No way" << '\n';else cout << "OK" << '\n';}}} int main(){ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);int T = 1;//cin >> T;while (T --) solve();return 0;}

本文作者：Natural-TLP

本文链接：https://www.cnblogs.com/Natural-TLP/p/19040466

版权声明：本作品采用知识共享署名-非商业性使用-禁止演绎 2.5 中国大陆许可协议进行许可。

网址：CCCC团体程序设计天梯赛 L2 https://klqsh.com/news/view/159504

相关内容

创意楼梯间及家居布局设计，提升居家舒适感
设计大赛
数字运动潮玩馆设计：打造城市新地标的赛博密码
顶流团队的“电梯罗生门”：饭圈修罗场里的真相博弈
智能工程与创意设计
社区生活里的支付宝小程序
快乐文化民俗体验教学设计.docx
惊艳无数人的金发造型 是顶程序自己参与设计的！
走进通力电梯，寻找数字化转型成功“秘籍”
揭秘Zigbee设备驱动程序编写：轻松入门与实战技巧

随便看看