Mike的农场
2024-09-05 19:45:26
题目
Mike有一个农场,这个农场n个牲畜围栏,现在他想在每个牲畜围栏中养一只动物,每只动物可以是牛或羊,并且每个牲畜围栏中的饲养条件都不同,其中第i个牲畜围栏中的动物长大后,每只牛可以卖a[i]元,每只羊可以卖b[i]元,为了防止牛羊之间相互影响,Mike找到了m条规律,每条规律给出一个三元组(i, j, k)表示如果第i个围栏和第j个围栏养的是不同的动物,那么Mike就需要花费k的代价请人帮忙处理牛羊之间的影响。不过同时Mike也发现k条特殊的规则(S, a, b),表示如果S中所有牲畜围栏中都养的是动物a,那么Mike可以获得b的额外收入。
现在Mike想知道他该在哪些围栏中饲养什么动物才能使得总收益最大,为了简化问题,你只需要输出最大收益。
分析
这道题用到最小割算法。
我们定义\(s\)和\(t\)为源点和汇点。
对于每个点\(i\),从\(s\)向\(i\)连一条容量为\(a[i]\)的边,从\(i\)向\(t\)连一条容量为\(b[i]\)的边。
对于每个规律\((i,j,k)\),\(i\)向\(j\)连一条容量为\(k\)的边,\(j\)向\(i\)连一条容量为\(k\)的边。
对于每个规则\((S,a,b)\),先建立一个新的点\(e\),分两种情况:
如果a=0,从\(s\)向\(e\)连一条容量为\(b\)的边,再从\(e\)向\(S\)集合中的每一个点连一条容量为\(∞\)的边。
如果a=1,从\(e\)向\(t\)连一条容量为\(b\)的边,再从\(S\)集合中的每一个点向\(e\)连一条容量为\(∞\)的边。
ok了。
网络流,
dinic会超时,用SAP+GAP。
最新文章
- 使用.net 创建windows service
- 让DB2跑得更快——DB2内部解析与性能优化
- [C语言]一个很实用的服务端和客户端进行UDP通信的实例
- 在WebBrowser中通过模拟键盘鼠标操控网页中的文件上传控件(转)
- Velocity(3)——字面值和转义
- Examining Open vSwitch Traffic Patterns
- StopWatch
- 利用System V消息队列实现回射客户/服务器
- Activity详细解释(生命周期、以各种方式启动Activity、状态保存,等完全退出)
- [原] 细说 NUMA
- PS+HTML测试
- 前端js总结
- Xml的用途
- tensorflow 笔记13:了解机器翻译,google NMT,Attention
- flask下载文件中文IE,Edge,Safari文件名乱码
- vue使用树形控件z-tree,动态添加数据,默认展开第一行
- Django Model._meta API
- Window 10 :我的性能优化:那效果,杠杠的!
- 杭电oj题目分类
- python学习笔记5--random
热门文章
- httpd启动显示Could not reliably determine the server's fully qualified domain name, using 127.0.0.1. Set the 'ServerName'
- Maven使用WEB-INF/lib下面的jar编译和打包
- TCP中SYN洪水攻击
- Docker中的Dockerfile命令详解FROM RUN COPY ADD ENTRYPOINT...
- exists、in和join比较
- ^A '\001' 分隔符
- [2019上海网络赛F题]Rhyme scheme
- python中输入某年某月某日,判断这一天是这一年的第几天?
- vue.js学习记录
- HDU - 1845 Jimmy’s Assignment (二分匹配)