D. The Number of Imposters(二分图染色)
Problem - D - Codeforces

Theofanis开始玩名为“Among them”的新网络游戏。然而,他总是和塞浦路斯球员一起踢球,他们都有一个相同的名字:“安德烈亚斯”(塞浦路斯最常见的名字)。在每个游戏中,Theofanis和n个其他玩家一起玩。因为它们都有相同的名字,所以编号从1到n。玩家在聊天中写下了m条评论。注释的结构是"i j c",其中i和j是两个不同的整数,c是一个字符串(1 < i, j < n;我j;C不是冒名顶替者就是船员)。注释的意思是玩家i说玩家j扮演角色c。冒名顶替者总是撒谎,而船员总是说真话。帮助Theofanis找出所有其他塞浦路斯玩家中冒名顶替者的最大可能数量,或者确定评论彼此矛盾(参见注释中的进一步解释)。注意,每个玩家只有一个角色:冒名顶替者或船员。输入第一行包含一个整数t (1 < t < 104)——测试用例的数量。下面是每个测试用例的描述。每个测试用例的第一行包含两个整数n和m (1 < n <2-105;0 <m <5-105) -除Theofanis之外的玩家数量和评论数量。接下来的m行每一行都包含一个由结构为“i j c”的玩家所做的评论,其中i和j是两个不同的整数,c是一个字符串(1 < i, j≤n;I # j;C不是冒名顶替者就是船员)。同一对(i, j)可以有多个注释。保证所有n的和不超过2-105,所有m的和不超过5 -105。输出对于每个测试用例,打印冒名顶替者的最大可能数量的整数。如果注释相互矛盾,则打印-1。
Example
input
Copy
5 3 2 1 2 imposter 2 3 crewmate 5 4 1 3 crewmate 2 5 crewmate 2 4 imposter 3 4 imposter 2 2 1 2 imposter 2 1 crewmate 3 5 1 2 imposter 1 2 imposter 3 2 crewmate 3 2 crewmate 1 3 imposter 5 0
output
Copy
2 4 -1 2 5
题解:
首先我们应该知道一个很重要的规律,如果c是crewmate(后面用1代表),a和b身份相同,否则身份不同
假设a -> b 1
1.a = 1,b = 1
2.a = 0,b = 0
假设a- >b 0
1.a = 1,b = 0
2.a = 0,b = 1
根据这个性质,我们可以建造一个二分图
如果两点身份不同,直接连边
如果两点身份相同,建造一个虚点,并且两边
最后利用染色法,看构建的二分图是否有冲突即可
#include<iostream>
#include<string>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
#define int long long
typedef pair<int,int> PII;
int col[1000060];
vector <int> p[1000060];
int ca,cb;
int n,m;
int dfs(int x,int c)
{col[x] = c;if(x <= n){if(c == 1)ca++;elsecb++;}for(auto ne:p[x]){if(!col[ne]){if(!dfs(ne,3 - c))return 0;}else if(col[ne] == col[x])return 0;}return 1;
}
void solve()
{cin >> n >> m;int ans = 0;for(int i = 1;i <= n + m;i++){p[i].clear();col[i] = 0;}int n1 = n;for(int i = 1;i <= m;i++){int a,b;string c;cin >> a >> b >> c;if(c[0] == 'i'){p[a].push_back(b);p[b].push_back(a);}else{++n1;p[a].push_back(n1);p[n1].push_back(a);p[b].push_back(n1);p[n1].push_back(b);}}for(int i = 1;i <= n1;i++){if(col[i])continue;ca = 0,cb = 0;if(dfs(i,1)){ans += max(ca,cb);}else{cout <<"-1\n";return ;}}cout << ans <<"\n";}
signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);int t = 1;cin >> t;
// scanf("%lld",&t);while (t--) {solve();}return 0;
}
相关文章:
D. The Number of Imposters(二分图染色)
Problem - D - Codeforces Theofanis开始玩名为“Among them”的新网络游戏。然而,他总是和塞浦路斯球员一起踢球,他们都有一个相同的名字:“安德烈亚斯”(塞浦路斯最常见的名字)。在每个游戏中,Theofanis和n个其他玩家一起玩。因为它们都有相…...
图片太大怎么改小kb?简单的图片压缩方法分享
平时当我们在朋友圈分享一些有趣的照片或者使用图片素材进行上传的时候,经常遇到图片大小kb超出平台限制的情况,这时就无法正常上传了,遇到这种情况我们就需要想办法降低图片大小kb,那么有什么办法能够压缩图片大小呢?…...
【python-leecode刷题】动态规划类问题----以53. 最大子数组和为例
作者:20岁爱吃必胜客(坤制作人),近十年开发经验, 跨域学习者,目前于海外某世界知名高校就读计算机相关专业。荣誉:阿里云博客专家认证、腾讯开发者社区优质创作者,在CTF省赛校赛多次取得好成绩。…...
Idea常用快捷键设置
设置来源于尚硅谷宋红康老师 第1组:通用型 说明 快捷键 复制代码-copy ctrl c 粘贴-paste ctrl v 剪切-cut ctrl x 撤销-undo ctrl z 反撤销-redo ctrl shift z 保存-save all ctrl s 全选-select all ctrl a 第2组:提高编写速度(上…...
【新2023Q2模拟题JAVA】华为OD机试 - 分苹果
最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为od机试,独家整理 已参加机试人员的实战技巧本篇题解:分苹果 题目 AB两个人把苹果…...
【博学谷学习记录】超强总结,用心分享丨人工智能 自然语言处理 BERT、GPT、ELMO对比学习简记
目录三模型架构BERTGPTELMO三者差异点三模型架构 BERT 优点 在11个NLP任务上取得SOAT成绩.利用了Transformer的并行化能力以及长语句捕捉语义依赖和结构依赖.BERT实现了双向Transformer并为后续的微调任务留出足够的空间. 缺点 BERT模型太大, 太慢.BERT模型中的中文模型是以…...
【嵌入式Bluetooth应用开发笔记】第四篇:初探蓝牙HOST及应用开发(持续更新ing)
概念 蓝牙HOST(Bluetooth Host)是指能够连接到其他蓝牙设备并控制它们的设备。在蓝牙技术中,通常有两种类型的设备:蓝牙HOST和蓝牙SLAVE。蓝牙HOST通常是指拥有控制权的设备,它可以主动连接其他蓝牙设备并向其发送命令。相反,蓝牙SLAVE则是指被动连接的设备,它接受来自…...
GORM 基础 -- CRUD 接口
1、Create 1.1 创建纪录 user : User{Name: "Jinzhu", Age: 18, Birthday: time.Now()}result : db.Create(&user) // pass pointer of data to Createuser.ID // 回填插入数据的主键 result.Error // 返回的 error 信息 result.RowsAffect…...
为什么0代码自动化测试越来越受欢迎?一文2000字解析
目录 01、什么是零代码自动化测试 02、为什么零代码自动化测试越来越受欢迎 03、有代码和零代码自动化有什么区别 04、零代码自动化测试可以帮助你做什么 05、零代码自动化测试方法:NLP(自然语言处理) 06、为什么我们需要零代码自动化测…...
cleanmymac最新2023版 mac清理软件CleanMyMac X4.12.5 中文版功能介绍
CleanMyMac X4.12.5 中文版只需两个简单步骤就可以把系统里那些乱七八糟的无用文件统统清理掉,节省宝贵的磁盘空间。cleanmymac x个人认为X代表界面上的最大升级,功能方面有更多增加,与最新macOS系统更加兼容,流畅地与系统性能更加…...
pyhon部署注意事项
前言:相信看到这篇文章的小伙伴都或多或少有一些编程基础,懂得一些linux的基本命令了吧,本篇文章将带领大家服务器如何部署一个使用django框架开发的一个网站进行云服务器端的部署。 文章使用到的的工具 Python:一种编程语言&…...
宣城x移动云,打造“城市级物联感知平台”
随着新一代信息技术与城市现代化的深度融合,智慧城市建设的重要性也愈发凸显。而在智慧城市建设中,物联网感知体系扮演着中枢神经系统的角色。 安徽宣城紧抓长三角城市群一体化发展机遇,为构建“数字宣城”建设发展新模式,携手移…...
英伟达Jetson NX套件刷机,配置Ubuntu20。
0. 前言 人并没有眼见得那么光鲜亮丽,博客也是。 今天推荐一本书《一百个人的十年》,没错就是我们的那十年(60年代)。写得很真实,牛棚猪圈,确实如此。 1. SdkManager安装 官网下载。 打开终端 执行命令sud…...
Vue计算属性
计算属性 计算属性的重点突出在属性两个字上(属性是名词),首先它是个属性其次这个属性有计算的能力(计算是动词),这里的计算就是个函数;简单点说,它就是一个能够将计算结果缓存起来的属性(将行为转化成了静态的属性),仅此而已…...
代码随想录刷题-字符串-反转字符串
文章目录反转字符串习题双指针swap 的两种方式反转字符串 本节对应代码随想录中:代码随想录,讲解视频:字符串基础操作! | LeetCode:344.反转字符串_哔哩哔哩_bilibili 习题 题目链接:344. 反转字符串 - …...
14-链表练习-剑指 Offer II 021. 删除链表的倒数第 n 个结点
题目 给定一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 示例 1: 输入:head [1,2,3,4,5], n 2 输出:[1,2,3,5] 示例 2: 输入:head [1], n 1 输出:[] 示例 3&…...
用Java解决华为OD机试考题,真的高效,真的强,来吧,清单奉上,祝你上岸
华为 OD 机试题最新(Java)清单(机试题库还在逐日更新) 题库目录 直接在本页使用 CtrlF,输入题目名称就可以进行检索。 序号文章分值1【华为OD机试真题JAVA】快递装载问题_国服第二切图仔的博客-CSDN博客1002【华为…...
【Stable Diffusion】Stable Diffusion免安装在线部署教程
一、开启Google Colab网址 官网:https://colab.research.google.com/ 点击添加代码: 二、执行如下代码指令 !pip install --upgrade fastapi0.90.1 !git clone https://github.com/AUTOMATIC1111/stable-diffusion-webui !git clone https://github.…...
Jetson设备如何接调试串口工具查看内核打印信息
方便小白使用如下教程。 一、认识USB转串口调试工具转接小板 和硬件连接方式 如图,是一款USB TO TTL转换板,这款小板支持3种供电模式:对外输出5V、对外输出3.3V和由外部供电。正面有一个跳帽,跳帽跳到3V3,小板由US…...
一直被低估的美图,正悄悄成为AIGC领跑者
【潮汐商业评论/原创】 也许多年之后再回望历史,2023年将被视为标志性的一年。它不仅是疫情之后的复苏之年,更是人工智能在中国乃至全球迎来爆发的一年。 从来没有这样的景象——在2023年的前3个月,全球互联网被AIGC话题“刷屏”࿰…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
4. TypeScript 类型推断与类型组合
一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式,自动确定它们的类型。 这一特性减少了显式类型注解的需要,在保持类型安全的同时简化了代码。通过分析上下文和初始值,TypeSc…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
