注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

一个蒟蒻的代码回收站

最后一次省选求rp

 
 
 

日志

 
 

bzoj1458士兵占领解题报告  

2014-04-28 15:02:00|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目链接

这题的无解应该很好判吧。把每个能放的点都放上去,如果还不行就是无解。

然后我们考虑从全部放上去的状态上拿掉一些,使其最优。

设行i最多能放x[i]个,列i最多能放y[i]个、

我们把每个行和列变成一个点,从源点到行i连一条x[i]-l[i]的边,列i向汇点连一条y[i]-r[i]的边,如果(x,y)能放,则x向y连一条容量为1的边(最多能拿掉一个)然后跑最大流。

这样跑出来的就是这个图最多能拿掉多少士兵。

然后就用最多能放的减去最大流。


#include<cstdio>
  评论这张
 
阅读(0)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017