费用流学习笔记

图论 学习笔记

题单

洛谷

• 【模板】最小费用最大流：模板题
• [国家集训队]航班安排：要考虑的比较复杂
• 方格取数加强版：拆点裸题
• [SCOI2007]修车：拆点很妙，裸题
• [HAOI2010]订货：裸题
• 航空路线问题：拆点，要输出方案
• 火星探险问题：拆点，输出方案很毒瘤，注意nm是反的
• [CQOI2012]交换棋子：有的人拆两个点，有的人拆三个点，但是都很妙
• 数字梯形问题：要建三次图，覆盖比较全面
• 运输问题：裸题
• [SNOI2019]通信

• [NOI2008]志愿者招募：想法比较妙
• [NOI2012]美食节
• [POI2006]SZK-Schools：裸题
• [SDOI2009]晨跑：裸题
• [SDOI2010]星际竞速：最小路径覆盖好题
• [SDOI2006]仓库管理员的烦恼：裸题
• [SDOI2017]新生舞会
• [TJOI2014]匹配
• [BJOI2012]连连看
• [JSOI2009]球队收益 / 球队预算
• [WC2007]剪刀石头布
• [ZJOI2011]营救皮卡丘
• 洞穴遇险
• 玉座の間
• Gosha is hunting
• 无限之环
• 深海机器人问题：输入过于毒瘤
• 餐巾计划问题：连边比较好
• 分配问题：裸题
• 汽车加油行驶问题
• 最长k可重区间集问题：一流对多流好题
• 最长k可重线段集问题

• [ZJOI2010]网络扩容：最大流+费用流

POJ

• Going Home：裸题
• Farm Tour
• Evacuation Plan
• The Windy's
• Minimum Cost
• Kaka's Matrix Travels

HDU

• Going Home：裸题
• Transportation
• Random Maze
• My Brute
• Special Fish
• Matrix Again