终于过了。。。

我觉得在HINT里面加个故事比较好

比如最后得到的结果奇贵，经理不干，于是买餐巾纸，但是餐巾纸涨价（啥MJ升天，MJ迷疯狂购买餐巾纸擦眼泪），于是经理要求大家自己带毛巾，被员工暴打-_-

比较符合标题

网络流不好想，线性规划一眼就能看出来，而且数据规模也不是巨大，所以用线性规划好像不错-_-

编译通过...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

数组开小,两次AC。

原题 USACO NOV08 GOLD PROB4

原题数据范围 n

这题可以先贪心构造初始流，假设全部毛巾都买，然后反向增广若干次，直到费用小于0

详见JK神牛的论文...

1.首先建立源S 汇T.

2.把N天拆点I->I',I->I'连一条费用为0 容量上界为Ni,下界也为Ni的弧.

3.S->1连条容量为+∞,费用为买新毛巾费用的边.(集中在第一天买)

4.所有I'->T连一条容量上界为Ni的边,费用为0.(用完就丢,可耻的浪费!!)

5.从第I->I+1连一条容量为+∞,费用为0的边.

6.从第I'->I+A连一条+∞,费用为fa的边

7.从第I'->I+B连一条+∞,费用为fb的边

最后求解有上下界flowcost...

======================================================/华丽的分割线

优化:

1.这个图有个大大的好处(发现几乎每道有上下界的WS流都有这种WS的方法),这个图很特别,必要弧上界下界相等,切可独立连至T...所以直接贪心初始流...让每条必要弧饱和,切每次费用全从S->1(也就是不用A,B直接浪费)...

2. (1)完以后你画看残留图,你会神奇的发现最后只需要从T->S找可退流的弧,且费用(每次SPFA后)为最小的至费用>=0....这样就很简单了

补充:

1.这题必有线性规划的解法,和去年NOI那道WS的志愿者招募一样.....志愿者是其加强版....

2.超囧的事,集训队论文居然有错别字,而且我在语文课上看后,被捉她说的....

。。。。这题拆点做划算。。。

膜拜用上下界的神牛

终于AC了，多谢curimit的提示……

WA了很多次，最后发现SPFA写错了，囧……

终于！Vag 6K都0MS了！！！！！

7KB 252行 单纯形法+一大堆优化=AC！

贪心???

MS题目与血案没什么关系，噱头啊

那位大牛 给个答案

哭求！！！！！！！！！！！！！

感激不尽

原来只有5个点。。。好无语。。。

最小费用最大流?

这题．．无语了

交三次

第一次40分，128错误,原来是数组开小了,开了200*200,T=N*2+1=201时萎了

第一次80分还是128错误,找了半天竟然i+b+1打成了i+b+a,这样都有80分..

...我太菜了,错误百出啊

这题的是可以用简单的最小费用最大流做的,

jingzi大牛用的是有上下界的费用流

都拆点,i拆成i,i+n

点内流量为当天需要的毛巾数

相邻点都连起来,表示当天消毒完的毛巾在后来也可以用

n+i与i+a+1,i+b+1连起来,表示毛巾消毒,费用为FA-F,FB-F(想一想为什么);

然后SPFA,当可改进量>=0时就该退出了

ANS=总的毛巾数*F+可改进量(为负)*相应费用