Day5费用流
2024-08-31 13:20:13
算法
zkw费用流:多路增广,增光D[y]=D[i]+c的边
无源汇上下界最小费用可行流
每次强行增加下界的流量
类似网络流,拆边
原边的费用为c,拆出来的边费用为0
负边和负圈
直接应用
SDOI2016数字配对
我的思路:
建出i*bi个点,如果ai是aj的质数倍,从bi个点向bj个点连边
跑有上下界可行费用最大流(woc这是个什么东西。。)
正解
两个数能够配对,分解后指数之和差为1则可以匹配
按照差值分为两类
不断增广
WF2011
有上下界最大费用最大流
——》限制相等的情况,可以通过加一维费用来解决
时间复杂度:$N^5$
回路问题
TJOI2013
对于回路上的点,其出度入度都为1
根据题意,每个点的出度都为1
我的思路:
找出入度不为1的点,$2^n$枚举是否更改(好傻逼)
正解
黑白染色,建二分图
从一个点向四个方向连边,(1,0) (1,1)(1,1) (1,1)
Topcoder
黑白染色后对度数进行限制
考虑如何处理费用
拆点,把一个点拆成两个,连流量为1的边,如果是直的,那么一定会经过中间的边,问题便可以得到解决
费用递增
美食节
JSOI2009球队XX
平方的性质满足费用递增
WC2007
签到问题
二分图模型
网络流24题
按照天数建点
每一天有三种方案
SDOI2010星际竞速
ZJOI2011
线性规划
志愿者招募
对于每个区间,分别列出等式
对每个等式进行差分
可以看到差分后数组左边的每个变量都出现了两次
Caught for a cat
GG
模拟费用流
Codeforce
XXXXXXXXXXXXXXXX
二叉树
最新文章
- 如何搞定IE+google双内核的360浏览器表单自动回填兼容问题
- ClassNotFoundException: com.fasterxml.jackson.databind.ObjectMapper的解决办法
- HttpWatch详解
- ACCESS的System.Data.OleDb.OleDbException: INSERT INTO 语句的语法错误
- VS2010不能打开预编译的网站源码的原因是什么?(转之csdn)
- [kmp+dp] hdu 4628 Pieces
- C# 语言规范_版本5.0 (第13章 接口)
- Bootstrap选项卡
- tomcat 日志 按天自动分割 设定时任务定时清除
- 快速掌握Oracle异常
- 视频显著性检测-----Predicting Video Saliency using Object-to-Motion CNN and Two-layer Convolutional LSTM
- Neutron 网络基本概念
- 转:在Struts 2中实现文件上传
- IP的计算
- python之多线程 queue 实践 筛选有效url
- Python常用模块os &; sys &; shutil模块
- Emacs中使用shell(调出terminal)
- word 中如何取消格式标记
- PHP自动加载SPL的四种处理方式
- redis 五大数据类型以及操作
热门文章
- javascript 优秀写法
- 51Nod 1433 0和5(数论)
- js中return 、return false 、return true、break、continue区别
- Android布局之FrameLayout
- BestCoder Round #11 (Div. 2)
- 关于App程序猿泡沫
- Android中System.currentTimeMillis()
- 翻翻git之---炫酷的自己定义翻滚View TagCloudView
- 九度OJ 1070 今年的第几天?(模拟)
- 在Fedora18上配置个人的Hadoop开发环境