P4311 士兵占领[最大流]
2024-09-29 04:46:37
有一个$M * N$的棋盘，有的格子是障碍。现在你要选择一些格子来放置一些士兵，一个格子里最多可以放置一个士兵，障碍格里不能放置士兵。我们称这些士兵占领了整个棋盘当满足第i行至少放置了$L_i$个士兵, 第j列至少放置了$C_j$个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘。
考虑到说棋盘问题，选的行和列之间是有关联的，彼此制约着数量，就应该可以从网络流入手（然而如果我不是奔网络流刷题来的说不定会瞎写一发dp）
最小化答案，应该对应的是最大流的反向转化（也就是化加为减，求减数最大值，如最小路径覆盖），要不然就是最小割。反正这题辣鸡我是想了一会最小割没想出来才去转化问题的。最少要摆多少个，可以看成把棋盘能摆满的都摆满，再去删去没必要的点。这样的话构建二分图，左点集表示每行，右点集是列。s点向左点集连边容量为$n-L_i-x$ x表示本行障碍数量。容量意思就是我这行最多可以删
最新文章
- TFS 测试用例步骤数据统计
- Ionic 今天发布了Windows 桌面版的IDE Ionic Lab
- android ImageSwitcher
- delphi ExecWB
- 一分钟明确 VS manifest 原理
- CSS之Position详解
- (转)jQuery验证控件jquery.validate.js使用说明+中文API
- LeetCode OJ 154. Find Minimum in Rotated Sorted Array II
- MySQL关于check约束无效的解决办法
- linux下安装node
- Win10下Docker学习（1）安装
- SQL Server判断是否满足日期格式（YYYYMMDD）以及中文等判断，格式化为YYYY-MM-DD
- Emit方式调用方法
- jquery快速入门（二）
- Python——使用高德API获取指定城指定类别POI并实现XLSX文件合并
- Linux 切换用户
- Android中使用Lambda表达式开发
- http代理和SOCKS5代理的区别
- CUDA C Programming Guide 在线教程学习笔记 Part 9
- 百度地图API--Key的获得