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

二分图博弈

一张二分图,Alice和Bob每人走一步,不能重复走,谁不能走谁输

结论:若存在最大匹配不包含初始点,则Bob赢,否则Alice赢

在这里插入图片描述

以上图为例,红色为最大匹配。

首先对于Alice第一步只能走黑边。而Alice无论走到哪个点,都有一条红边。(不然就不是最大匹配了 )

那么Bob就走红边,此时回到左边,Alice就只能走黑边了。


实现上,我们先把初始点去掉跑一遍流,加上后在残余网络上再跑一遍

http://www.lryc.cn/news/194684.html

相关文章:

  • 【C++】C++11—— 包装器
  • LED显示屏高刷新率和低刷新率有什么区别
  • 国际伦敦银点差费值得吗?
  • 常见的作物模型应用技巧!DSSAT模型、APSIM模型、WOFOST模型与PCSE模型等应用
  • 2023年中国超硬材料制品分析及超硬刀具市场规模分析[图]
  • 使用React、Express实现一个问卷发布/收集系统
  • DDD之上下文映射图(Context Mapping)
  • CountDownLatch的原理
  • Java新特性Stream流详解
  • 关于VScode中一些常用的快捷操作!
  • Django 使用Mysql数据库
  • js继承的几种方式(原型链继承、构造函数继承、组合式继承、寄生组合式继承、ES6的Class类继承)
  • AnyTransition/过渡动画, MatchedGeometryEffect/匹配几何动画效果 的使用
  • mac版postman升级后数据恢复办法
  • 四.镜头知识之放大倍率
  • Jenkins UI 自动化持续化集成测试
  • vue项目中引入地图的详细教程
  • MyBatisPlus 多数据源配置
  • 使用Golang实现HTTP代理突破IP访问限制
  • Iterator和ListIterator的区别是什么?
  • 大坑-MATLAB图片转存时需注意的点
  • 基于Lang-Chain(ChatGLM和ChatChat)知识库大语言模型的部署搭建
  • 个人轻博客PHP开源系统/溯雪Sxlog轻博客源码/洁干净轻/占内存极低/php源码
  • 2.Vue-从零开始搭建一个vue项目
  • 快速构建代理应对
  • 【LeetCode刷题(数据结构)】:另一颗树的子树
  • LeetCode 2903. 找出满足差值条件的下标 I【双指针+维护最大最小】简单
  • 【神经网络】如何在Pytorch中从零开始将MNIST网络量化为8位
  • 智慧水利:山海鲸数字孪生的革新之路
  • 【unity】【VR】白马VR课堂系列-VR开发核心基础04-主体设置-XR Rig的引入和设置