当前位置: 首页 > news >正文

【学习笔记】POJ 3834 graph game

点这里

结论题😅 ,图一乐

结论:如果原图中存在两个边集不交的生成树,那么 Bob \text{Bob} Bob必胜;否则 Alice \text{Alice} Alice必胜

证明有点难😅

首先,考虑维护两颗 不存在红边 的生成树,如果 Alice \text{Alice} Alice断掉了其中一颗树上的一条边,将这个树分成两个连通块,那么 Bob \text{Bob} Bob一定可以在另一颗树上选择一条边变成蓝色,使得这个树再次联通,最终两个生成树都只由蓝边构成

其次,如果原图中不存在这样的两颗生成树,则考虑某次 Alice \text{Alice} Alice操作时, Bob \text{Bob} Bob胜利的条件:将所有蓝色的边 复制一遍,使得存在两个边集不交的生成树。假设存在某种策略,使得 Bob \text{Bob} Bob在某次操作后满足了这个条件,那么 Alice \text{Alice} Alice可以照搬 Bob \text{Bob} Bob的策略,使得某次操作后将红边复制一遍,使得存在两个边集不交的生成树。因此 Alice \text{Alice} Alice存在可以让红边构成一颗生成树的策略。又因为原图中不存在两个边集不交的生成树,因此 Bob \text{Bob} Bob无法胜利

有点绞

发现 ( 30 9 ) \binom{30}{9} (930)比较小,直接暴搜即可。

#include<cstdio>
#include<iostream>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define db double
#define ull unsigned long long
#define inf 0x3f3f3f3f
using namespace std;
int n,m,fa[10],fa2[10],U[30],V[30],s[30];
int find(int x){return fa[x]==x?x:find(fa[x]);
}
int check(){for(int i=0;i<n;i++)fa2[i]=fa[i],fa[i]=i;int tot=0;for(int i=0;i<m;i++){if(s[i]==0){int x=find(U[i]),y=find(V[i]);if(x!=y)fa[x]=y,tot++;}}if(tot==n-1){return 1;}for(int i=0;i<n;i++)fa[i]=fa2[i];return 0;
}
int dfs(int x,int y){if(y==n-1)return check();for(int i=x;i<m;i++){int a=find(U[i]),b=find(V[i]);if(a==b)continue;fa[a]=b,s[i]=1;if(dfs(i+1,y+1))return 1;fa[a]=a,s[i]=0;}return 0;
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);while(cin>>n>>m){if(n==-1&&m==-1)break;for(int i=0;i<n;i++)fa[i]=i;for(int i=0;i<m;i++)cin>>U[i]>>V[i],s[i]=0;cout<<(dfs(0,0)?"YES":"NO")<<"\n";}
}

相关文章:

【学习笔记】POJ 3834 graph game

点这里 结论题&#x1f605; &#xff0c;图一乐 结论&#xff1a;如果原图中存在两个边集不交的生成树&#xff0c;那么 Bob \text{Bob} Bob必胜&#xff1b;否则 Alice \text{Alice} Alice必胜 证明有点难&#x1f605; 首先&#xff0c;考虑维护两颗 不存在红边 的生成树…...

无监督学习算法Kmeans

1. 有监督学习和无监督学习 在机器学习算法中&#xff0c;常把算法分为有监督学习和无监督学习两种。他们之间的区别主要在于输入数据集类型和学习目标。 &#xff08;1&#xff09;有监督学习&#xff1a;训练输入的数据需要带有标签&#xff0c;以便算法能够学习输入和输出…...

区块链(4):区块链技术模型介绍

1 区块链白皮书中的公有链&#xff0c;私有链&#xff0c;联盟链概念介绍 区块链系统根据应用场景和设计体系的不同&#xff0c;一般分为公有链、联盟 链和专有链(私有链)。其中: 公有链的各个节点可以自由加入和退出网络&#xff0c;并参加链上数据的读 写&#xff0c;运行时…...

go语言 rune 类型

ASCII 码只需要 7 bit 就能完整地表示&#xff0c;但只能表示英文字母在内的 128 个字符&#xff0c;为了表示世界上大部分的文字系统&#xff0c;发明了 Unicode &#xff0c;它是 ASCII 的超集&#xff0c;包含世界上书写系统中存在的所有字符&#xff0c;并且为每个代码分配…...

DS18B20温度传感器

DS18B20简介 DS18B20 是由 DALLAS 半导体公司推出的一种的“一线总线&#xff08;单总线&#xff09;”接口的温度传感器 这种一线总线就是 三线制 SPI DS18B20的 配置寄存器&#xff1a; TM 是测试位&#xff0c;出厂设置就被设置为0&#xff0c;不需要改动&#xff0c; R1、R…...

LeetCode322. 零钱兑换

322. 零钱兑换 文章目录 [322. 零钱兑换](https://leetcode.cn/problems/coin-change/)一、题目二、题解方法一&#xff1a;完全背包二维数组方法二&#xff1a;一维数组 三、注意 一、题目 给你一个整数数组 coins &#xff0c;表示不同面额的硬币&#xff1b;以及一个整数 a…...

AUTOSAR扫盲贴--不是黑神话【基本概念和方法论】

猴子纵有72搬变化,也跳不出如来的手掌 目录 1. 引言 2. AUTOSAR的基本概念 2.1. AUTOSAR的架构和组成部分 2.2. AUTOSAR的规范和...

python抠图(去水印)开源库lama-cleaner入门应用实践

1. 关于 Lama Cleaner Lama Cleaner 是由 SOTA AI 模型提供支持的免费开源图像修复工具。可以从图片中移除任何不需要的物体、缺陷和人&#xff0c;或者擦除并替换&#xff08;powered by stable diffusion&#xff09;图片上的任何东西。 特征&#xff1a; 完全免费开源&am…...

Nginx可视化管理工具结合cpolar实现远程访问内网服务

前言 Nginx Proxy Manager 是一个开源的反向代理工具&#xff0c;不需要了解太多 Nginx 或 Letsencrypt 的相关知识&#xff0c;即可快速将你的服务暴露到外部环境&#xff0c;并且支持 SSL 配置。基于 Tabler 的美观且安全的管理界面,无需了解 Nginx 即可轻松创建转发域、重定…...

CCC数字钥匙设计【BLE】 --建立安全测距

1、建立安全测距Establish Secure Ranging 车端总共有三种建立安全测距的方式&#xff0c;具体如下&#xff1a; 1) Optimal Flow 2) Sub-Optimal Flow 3) Ranging Recovery Flow 为了确定建立安全测距需要执行哪条流程&#xff0c;车辆需要进行以下流程选择。当车辆和设备…...

Ubuntu22.04 Opencv4.5.1 CPU和GPU编译攻略,Opencv CPU和GPU编译保姆教程 亲自测试。

1、安装opencv依赖 安装时最好更换一下源。 sudo apt-get -y update sudo apt-get -y install cmake git libgtk2.0-dev pkg-config libavcodec-dev libavformat-dev libswscale-dev sudo apt-get -y install libgtk-3-dev gfortran openexr libatlas-base-dev python3-dev pyt…...

常识判断 --- 党史

目录 中共1~3大 例题 国民党 例题 中共4~5大 例题 中共起义~会议 例题 中共六届六中全会&#xff08;1938年9月&#xff09; 中共七大&#xff08;1945年4月&#xff09; 例题 中共七届二中全会 例题 中共8~10大 中共11~12届全会 例题 中共13~14大 …...

Rust 基础再理解

Rust堆栈 Rust中各种类型的值默认都存储在栈中&#xff0c;除非显式地使用Box::new()将它们存放在堆上&#xff0c;但数据要存放在栈中&#xff0c;要求其数据类型的大小已知。对于静态大小的类型&#xff0c;可直接存储在栈上&#xff0c;如裸指针、布尔、字符、整数浮点数&a…...

Opencv cuda版本在ubuntu22.04中安装办法,解决Could NOT find CUDNN的办法

文章目录 概要下载cuda的runfile版本配置环境变量官网下载cudann安装Opencv依赖包下载opencv和opencv_contrib并解压准备编译安装anaconda环境执行编译命令安装OpenCV并检查是否安装成功 概要 解决以下安装问题&#xff1a; -- Could NOT find CUDNN: Found unsuitable versi…...

全网首发YOLOv8暴力涨点:Gold-YOLO,遥遥领先,超越所有YOLO | 华为诺亚NeurIPS23

💡💡💡本文独家改进:提出了全新的信息聚集-分发(Gather-and-Distribute Mechanism)GD机制,Gold-YOLO,替换yolov8 head部分 实现暴力涨点 Gold-YOLO | 亲测在多个数据集能够实现大幅涨点 💡💡💡Yolov8魔术师,独家首发创新(原创),适用于Yolov5、Yolov7、…...

BD就业复习第四天

1. 布隆过滤器怎么实现去重 布隆过滤器是一种用于快速检查一个元素是否可能存在于一个大集合中的数据结构&#xff0c;但它并不适用于精确去重。因为布隆过滤器具有一定的误判率&#xff08;可能会将不存在的元素误判为存在&#xff09;&#xff0c;所以不能确保完全的去重。但…...

数据结构 | 树

树 树是n&#xff08;n>0&#xff09;个结点的有限集。当n 0时&#xff0c;称为空树。在任意一棵非空树中应满足&#xff1a; 有且仅有一个特定的称为根的结点。当n>1时&#xff0c;其余节点可分为m&#xff08;m>0&#xff09;个互不相交的有限集T1,T2,…,Tm&#…...

Android11 适配

一、修改targetSdkVersion为30 将build.gradle的目标版本targetSdkVersion修改为30&#xff08;Android 11&#xff09; targetSdkVersion 30Android11的改变改变主要影响以Adnroid11 为目标版本的应用&#xff08;targetSdkVersion>30才有影响&#xff09;&#xff0c;和所…...

UML基础与应用之对象图

什么是对象图&#xff1f; 对象图表示一组对象及它们之间的关系&#xff0c;是某一时刻系统详细信息的快照&#xff0c;描述系统交互的静态图形&#xff0c;它由协作的对象组成&#xff0c;但不包含在对象之间传递的任何消息。因为对象是类的实例化&#xff0c;所以说某一时刻…...

英码科技精彩亮相火爆的IOTE 2023,多面赋能AIoT产业发展!

9月20日至22日&#xff0c;在这金秋飒爽的季节&#xff0c;为期三天的IOTE 2023第二十届国际物联网展深圳站在深圳国际会展中心盛大举行。英码科技精彩亮相本届展会&#xff0c;并在同期举办的AIoT视觉物联产业生态大会发表了主题演讲&#xff0c;与生态伙伴们共同探讨AIoT产业…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...