BZOJ 1305: [CQOI2009]dance跳舞( 最大流 )
云神代码很短...0 ms过的...看了代码 , 大概是贪心... orz 我不会证
数据这么小乱搞就可以了吧... ←_←
这道题网络流还是可以写的...
既然限制了最多只能和 k 个不喜欢的人dance , 那么就把每个人拆成 a , b 两个点 . 限制完了之后 , 因为 n <= 50 , 我们可以直接从从小到大枚举 , 一个一个增广 .
具体建图 :
boy_a( i ) -> boy_b( i ) ( cap : k ) , girl_b( i ) -> girl_a( i ) ( cap : k ) ( 1 <= i <= n )
对于两个人 boy( i ) , girl( j ) :
boy( i ) and girl( j ) are friends : boy_a( i ) -> girl_a( j ) ( 1 )
boy( i ) and girl( j ) aren't friends : boy_b( i ) -> girl_b( j ) ( 1 )
然后每次给 S -> boy_a( i ) , girl_a( i ) -> T ( 1 <= i <= n ) 加一条 1 的弧 , 跑一下看增加的流量是否为 n , 假如是就继续并将答案 + 1 , 不是就结束
-------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------
1305: [CQOI2009]dance跳舞
Time Limit: 5 Sec Memory Limit: 162 MB
Submit: 1863 Solved: 793
[Submit][Status][Discuss]
Description
一次舞会有n个男孩和n个女孩。每首曲子开始时,所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首(或更多)舞曲。有一些男孩女孩相互喜欢,而其他相互不喜欢(不会“单向喜欢”)。每个男孩最多只愿意和k个不喜欢的女孩跳舞,而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息,舞会最多能有几首舞曲?
Input
第一行包含两个整数n和k。以下n行每行包含n个字符,其中第i行第j个字符为'Y'当且仅当男孩i和女孩j相互喜欢。
Output
仅一个数,即舞曲数目的最大值。
Sample Input
YYY
YYY
YYY
Sample Output
HINT
N<=50 K<=30
Source
最新文章
- (Interface)接口特点
- dedecms最新版本修改任意管理员漏洞
- vJine 第三波 之 Lua 来袭 vJine.Lua
- [LeetCode]题解(python):005-Longest Palindromic Substring
- hdu 逆袭指数
- POJ 3070 矩阵快速幂解决fib问题
- js 中ajax请求时设置 http请求头中的x-requestd-with= ajax
- Python Xcode搭建Python环境以及使用PyCharm CE
- Redis sentinel &; cluster 原理分析
- Jenkins构建时间Poll Scm的设置
- 传输控制协议(TCP) -- 连接建立及终止过程
- Windows Server 2012 R2安装Oracle 11g问题
- 【转】Nginx 学习笔记(十一)nginx下安装配置naxsi waf防火墙(附完整编译、配置)
- Leetcode 树(102, 637)
- sping框架纯注解配置
- javascript:没有定义的变量和没有定义的属性
- 3d角色模型 制作 全过程 。3d max 。3d role model making process.3d Max
- vue cli 打包项目造成css背景图路径错误
- C#: 获取当前路径不要用Environment.CurrentDirectory
- json和jsonp的问题
热门文章
- I can do it!(贪心)
- GDAL1.9.1 IN VS2008 C#中的编译及使用
- IE升级到10.0,VS2010启动调试时报“未能将脚本调试器附加到计算机..”
- if语句判断身高体重是否标准
- Jquery调用webService的四种方法 转载-记录
- BZOJ 1880: [Sdoi2009]Elaxia的路线( 最短路 + dp )
- HTML5 事件
- 使用wget -i下载多个文件
- QT学习 之 文本文件读写
- Ultra-QuickSort(归并排序+离散化树状数组)