[费用流]猜测
猜测
Time Limit: 10 Sec Memory Limit: 256 MB
Description
Input
Output
Sample Input
3
1 1
1 2
2 1
Sample Output
3
explain:
(1,1),(1,1),(2,2)不是一个合法猜测(有相同的格子),因此不管怎么猜总是能全部猜中。
HINT
Main idea
给定了若干个标准点,用这些点的横纵坐标分为x集和y集,定义猜点表示从x集和y集中各选一个,不能猜出重复的点,问在所有合法方案中最少包含上述几个标准点。
Solution
我们看到了这道题目,考虑从费用流的方法下手。
我们从S->x集:容量为数字出现次数,费用为0;y集->T:容量为数字出现次数,费用为0;x集->y集:容量为1,若组合成了标准点则费用为1,否则为0。
然后我们这样连边,又由于题目要的是最少包含几个点,那么显然最小费用最大流就是答案了。
Code
12345678910111213141516171819202122232425262728293031323334 ...
[费用流]球队预算
球队预算
Time Limit: 10 Sec Memory Limit: 256 MB
Description
在一个篮球联赛里,有n支球队,
球队的支出是和他们的胜负场次有关系的,具体来说,第i支球队的赛季总支出是Cix^2+Diy^2,Di<=Ci。(赢得多,给球员的奖金就多嘛)
其中x,y分别表示这只球队本赛季的胜负场次。
现在赛季进行到了一半,每只球队分别取得了a[i]场胜利和b[i]场失利。
而接下来还有m场比赛要进行。
问联盟球队的最小总支出是多少。
Input
第一行n,m
接下来n行每行4个整数a[i],b[i],Ci,Di
再接下来m行每行两个整数s,t表示第s支队伍和第t支队伍之间将有一场比赛,注意两只队间可能有多场比赛。
Output
输出总值的最小值。
Sample Input
3 3
1 0 2 1
1 1 10 1
0 1 3 3
1 2
2 3
3 1
Sample Output
43
HINT
2<=n<=5000,0<=m<=1000,0<=di<=ci<=10,0< ...
[费用流]软件开发
软件开发
Time Limit: 10 Sec Memory Limit: 162 MB
Description
某软件公司正在规划一项n天的软件开发计划,根据开发计划第i天需要ni个软件开发人员,为了提高软件开发人员的效率,公司给软件人员提供了很多的服务,其中一项服务就是要为每个开发人员每天提供一块消毒毛巾,这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种,A种方式的消毒需要a天时间,B种方式的消毒需要b天(b>a),A种消毒方式的费用为每块毛巾fA, B种消毒方式的费用为每块毛巾fB,而买一块新毛巾的费用为f(新毛巾是已消毒的,当天可以使用);而且f>fA>fB。公司经理正在规划在这n天中,每天买多少块新毛巾、每天送多少块毛巾进行A种消毒和每天送多少块毛巾进行B种消毒。当然,公司经理希望费用最低。你的任务就是:为该软件公司计划每天买多少块毛巾、每天多少块毛巾进行A种消毒和多少毛巾进行B种消毒,使公司在这项n天的软件开发中,提供毛巾服务的总费用最低。
Input
第1行为n,a,b,f,fA,fB. 第2行为n1,n2,……,nn.
Output
...
[随机化]Sensor Network
Sensor Network
Time Limit: 2 Sec Memory Limit: 128 MB
Description
魔法炮来到了帝都,除了吃特色菜之外,还准备去尝一尝著名的北京烤鸭。
帝都一共有n个烤鸭店,可以看成是二维平面内的点。
不过由于魔法炮在吃烤鸭之前没有带钱,所以吃完烤鸭之后只能留下刷盘子。
刷完盘子之后,魔法炮除了不用付饭费之外,老板还会奖励他d元钱。
魔法炮是一个特么喜欢吃烤鸭的孩子,所以在去过一家烤鸭店之后,魔法炮还准备去其他的烤鸭店。
但是由于帝都路费较贵,每单位长度需要花费1元钱,所以魔法炮可能去不了所有其他的烤鸭店。
在到达下一家烤鸭店之前,魔法炮会花掉手里所有钱,以便于下一次接着吃霸王餐。
另外,魔法炮对于自己刷过盘子的烤鸭店有着特殊的感情,所以他要求在某一家烤鸭店吃完烤鸭后,可以到达全部已经吃过去过的烤鸭店。
那么问题来了,魔法炮想知道自己最多能去多少家烤鸭店,以及这些烤鸭店都是哪些。你能帮帮他吗?
Input
第一行两个整数n和d,分别表示烤鸭店数和老板给魔法炮的路费。
接下来n行,每行两个整数x,y,表示 ...