团体程序设计天梯赛 L2-010 排座位(并查集)

news/2024/4/24 14:28:15/文章来源:https://blog.csdn.net/X_StarX/article/details/136509424

L2-010 排座位

分数 25

布置宴席最微妙的事情,就是给前来参宴的各位宾客安排座位。无论如何,总不能把两个死对头排到同一张宴会桌旁!这个艰巨任务现在就交给你,对任何一对客人,请编写程序告诉主人他们是否能被安排同席。

输入格式:

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

这里假设朋友的朋友也是朋友。但敌人的敌人并不一定就是朋友,朋友的敌人也不一定是敌人。只有单纯直接的敌对关系才是绝对不能同席的。

输出格式:

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

输入样例:

7 8 4
5 6 1
2 7 -1
1 3 1
3 4 1
6 7 -1
1 2 1
1 4 1
2 3 -1
3 4
5 7
2 3
7 2

输出样例:

No problem
OK
OK but...
No way

题解 

根据题意,需要使用并查集把朋友都分类到一起,并且用一个数组记录他们是不是敌人。

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int f[105];
int d[105][105];//记录是否是敌人
//并查集
int find(int x)
{if(f[x]==x){return x;}f[x]=find(f[x]);return f[x];
}
int main()
{cin>>n>>m>>k;for(int i=1;i<=n;i++){f[i]=i;}while(m--){int a,b,op;cin>>a>>b>>op;if(op==1){int u=find(a);int v=find(b);if(u!=v){f[v]=u;//合并}}else{//是敌人d[a][b]=1;d[b][a]=1;}}while(k--){int a,b;cin>>a>>b;if(find(a)==find(b) && d[a][b]==0){cout<<"No problem"<<endl;}else if(find(a)!=find(b) && d[a][b]==0){cout<<"OK"<<endl;}else if(find(a)==find(b) && d[a][b]==1){cout<<"OK but..."<<endl;}else if(find(a)!=find(b) && d[a][b]==1){cout<<"No way"<<endl;}}return 0;} 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_996434.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Java面试/24春招】技术面试题的准备

Spring MVC的原理 Mybatis的多级缓存机制 线程池的大小和工作原理 上述问题&#xff0c;我们称为静态的问题&#xff0c;具有标准的答案&#xff0c;而且这个答案不会变化&#xff01; 如果没有Spring&#xff0c;会怎么样&#xff1f;IOC这个思想是解决什么问题&#xff1f…

男人的玩具系统wordpress外贸网站主题模板

垂钓用品wordpress外贸模板 鱼饵、鱼竿、支架、钓箱、渔线轮、鱼竿等垂钓用品wordpress外贸模板。 https://www.jianzhanpress.com/?p3973 身体清洁wordpress外贸网站模板 浴盐、防蚊液、足部护理、沐浴液、洗手液、泡澡用品wordpress外贸网站模板。 https://www.jianzhan…

基于OpenCV的图形分析辨认02

目录 一、前言 二、实验目的 三、实验内容 四、实验过程 一、前言 编程语言&#xff1a;Python&#xff0c;编程软件&#xff1a;vscode或pycharm&#xff0c;必备的第三方库&#xff1a;OpenCV&#xff0c;numpy&#xff0c;matplotlib&#xff0c;os等等。 关于OpenCV&…

关于比特币的AI对话

【ChatGPT】 比特币源码开源吗&#xff1f; 是的&#xff0c;比特币的源码是开源的。比特币项目是在MIT许可证下发布的&#xff0c;这意味着任何人都可以查看、修改、贡献和分发代码。比特币的源码托管在GitHub上&#xff0c;可以通过下面的链接进行访问&#xff1a; https://g…

Python】深度学习基础知识——随机梯度下降详解和示例

本文通过原理和示例对随机梯度下降进行了详解&#xff0c;并和梯度下降进行了对比分析&#xff0c;简单易懂。 随机梯度下降原理示例 动态学习率动态学习率示例 总结 随机梯度下降 原理 示例 import torch import torch.nn as nn import matplotlib.pyplot as pltdef train_2…

Day14:信息打点-主机架构蜜罐识别WAF识别端口扫描协议识别服务安全

目录 Web服务器&应用服务器差异性 WAF防火墙&安全防护&识别技术 蜜罐平台&安全防护&识别技术 思维导图 章节知识点 Web&#xff1a;语言/CMS/中间件/数据库/系统/WAF等 系统&#xff1a;操作系统/端口服务/网络环境/防火墙等 应用&#xff1a;APP对象/…

Codeforces Round 930 (Div. 2 ABCDEF题) 视频讲解

A. Shuffle Party Problem Statement You are given an array a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1​,a2​,…,an​. Initially, a i i a_ii ai​i for each 1 ≤ i ≤ n 1 \le i \le n 1≤i≤n. The operation swap ( k ) \texttt{swap}(k) swap(k) for an…

STM32 学习8 USART串口通讯与printf重定向

STM32 学习8 USART串口通讯 一、串口通信介绍1. USART介绍2. UART介绍3. STM32 F103ZET6串口资源4. STM32 USART作用5. STM32 USART框图引脚说明 6. 寄存器USART_SR&#xff08;Status Register&#xff0c;状态寄存器&#xff09;&#xff1a;USART_DR&#xff08;Data Regist…

算力调度和云计算有何区别

Canalys发布的研究报告显示&#xff0c;2023年第二季度&#xff0c;全球云基础设施服务支出增长16%&#xff0c;达到724亿美元。 此前云厂商们的高速增长&#xff0c;主要归功于大规模的企业数字化转型和上云。当前市场的增速放缓&#xff0c;除了上云普及带来的市场增量见顶&…

Nginx启动服务

Nginx启动服务 一、启动前置 下载地址 如已安装Docker&#xff0c;下一步拉取Nginx最新的Docker镜像&#xff1a; docker pull nginx:latest查看拉取下来的镜像&#xff1a; docker images二、启动服务 创建Docker容器&#xff1a; docker run --name {projectname} -p 80…

Springboot配置MySQL数据库

Springboot配置MySQL数据库 一、创建springboot项目&#xff0c;并添加如下依赖 <dependency><groupId>com.mysql</groupId><artifactId>mysql-connector-j</artifactId><scope>runtime</scope> </dependency>二、在applica…

AMDGPU KFD Test 编译使用

ROCT-Thunk-Interface是一个用于在ROCm软件堆栈中提供设备无关性的层。它是ROCm的一部分&#xff0c;允许不同的硬件平台&#xff08;如AMD GPU和Intel CPU&#xff09;使用相同的API进行计算。 要安装ROCT-Thunk-Interface&#xff0c;首先需要创建一个新的目录&#xff0c;并…

微信小程序开发系列(二十)·wxml语法·setData()修改对象类型数据、ES6 提供的展开运算符、delete和rest的用法

目录 1. 新增单个、多个属性 1.1 新增单个属性 1.2 新增多个属性 2. 修改单个、多个属性 2.1 修改单个属性 2.2 修改多个属性 3. 优化 3.1 ES6 提供的展开运算符 3.2 Object.assign()将多个对象合并为一个对象 4. 删除单个、多个属性 4.1 删除单个属性 …

跨链桥的类型总结/相关的名词解释

首先&#xff0c;这是一个会持续更新的文章&#xff0c;我会不断把自己了解到的跨链桥名词解释更新在这里。 跨链桥类型 基于传输方式分类&#xff1a; Lock and Mint&#xff1a;在一条链上锁定资产&#xff0c;在另一条链上铸造等价资产liqidity pool&#xff1a;在不同链…

Apifox

⭐⭐⭐ 推荐&#xff1a;人工智能助手 接口测试是软件开发过程中不可或缺的一环&#xff0c;它有助于确保各个系统组件能够正常交互&#xff0c;提高软件的质量和稳定性。随着现代软件开发趋向于微服务架构&#xff0c;接口测试变得更加重要。在众多接口测试工具中&#xff0c…

Android 日志原理解析

一、Logcat 二、Dumpsys C:\Users\pengcheng.ding>adb shell dumpsys --help usage: dumpsysTo dump all services. or:dumpsys [-t TIMEOUT] [--priority LEVEL] [--clients] [--dump] [--pid] [--thread] [--help | -l | --skip SERVICES | SERVICE [ARGS]]--help: show…

基于OpenCV的图形分析辨认01

目录 一、前言 二、实验目的 三、实验内容 四、实验过程 一、前言 编程语言&#xff1a;Python&#xff0c;编程软件&#xff1a;vscode或pycharm&#xff0c;必备的第三方库&#xff1a;OpenCV&#xff0c;numpy&#xff0c;matplotlib&#xff0c;os等等。 关于OpenCV&…

目标检测评估指标

目录 一、检测精度1、TP、FP、TN、FN概念正样本和负样本TP(True Positive---正确的正向预测)FP(False Positive---错误的正向预测&#xff09;FN(False Negative---错误的负向预测)TN(True Negative---正确的负向预测) 2、Precision(准确率)和Recall(召回率)3、P-R curve &…

【QT】自定义控件的示例

自定义控件&#xff08;很重要&#xff09; 什么是自定义控件&#xff1f; 顾名思义就是创建一个窗口&#xff0c;放入多个控件&#xff0c;拼接起来&#xff0c;一起使用。 为什么需要它&#xff1f; 需求&#xff0c;假设有100个窗口&#xff0c;那如果有两个控件同时被使…

RK 解决抖音 流行应用 摄像头画面裁剪放大

问题记录 SOC&#xff1a;RK3568 system&#xff1a;Android12 流行应用 一些APP通过打开板载摄像头出现画面裁剪 画面比例不正常或者是预览方向旋转&#xff0c;但是使用相机APP打开却不会 修改&#xff1a; hardware\interfaces\camera\device\3.4\default\RgaCropScale.…