[费用流训练] - cool's Blog

[费用流训练]

cool posted @ 2016年9月17日 17:05 in 图论 , 611 阅读

一直不会费用流,每天用单纯形骗分,被大骂一通,开始学习费用流。

费用流什么原理不是很清楚,但板子还是很好背的。

 

[方格取数]

矩阵每个元素最多取一次,从左上走到右下K次的权值最大值。

拆点,然后1条边是有费用的,流量1,其余边都是0费用,inf流量。

S向起点流K,终点向T流K。

[餐巾计划]

详见网络流24题。

拆点,i表示当天需要数,i'表示当天有多少没洗。

[bzoj3171循环格]

一个矩阵,每个格子连向一个相邻格,问至少改多少个连边,使从任意一个点出发都能回到该点。

最后一个条件即为,每个点出入度都为1。所以每个格子向原来连向的格子连0费用,1流量,其他连1费用,1流量即可。

[bzoj1070修车]

N个人修M辆车,求平均最小等待时间。

建图有点神,有点暴力的感觉。

把每个工人拆成N个点。记为A[i,j]表示第i个工人修倒数第j辆车。

每个车跟所有N*M个工人拆出的点连边。流量为1,费用为time[i,j]*k。

源和每辆车连边,N*M个点和汇连边,流量都为1,费用同为0。——by hzwer

 

bzoj2879是加强版,不过还没看懂,先留个坑。

 

[bzoj2324营救皮卡丘]

有K个人,先到了i-1点,才能走到i点,走到N点,问最短距离。

Floyd求出最短距离,且dis[i][j] = dis[i][k]+dis[k][j]的k不能比i,j都大。

又因为每个点都必须经过的,所以每个点都至少有1的流量,从S向i'流1就行了。

 

Meghalaya Board Mode 说:
2022年8月25日 18:38

Meghalaya Board Model Paper 2023 Class 8 Pdf Download with Answers for Bengali Medium, English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Meghalaya Board Model Paper Class 8Type Questions to Term1 & Term2 Exams at official website. New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.

Matthew Wade 说:
2025年2月24日 16:18

Thanks a lot for a fantastic blog post, exactly where will you come across all of your information? 代写

Matthew Wade 说:
2025年2月25日 23:35

Locate which will article writing is not actually valued at the time period, you might recognise that discovering them free of charge is really a lot a great deal more an individual’s idea! Precisely why craft content articles together with throw away your time and energy when you are able become terrific content absolutely free! A lot of people discover utilizing just a dash of effort paid out diving the web page and looking at what’s going on they is able to leave and reveal a whole lot of function done with the particular means available. Learnician

Jackson 说:
2025年3月09日 21:59

Thanks for your handy post. Over time, I have come to be able to understand that the particular symptoms of mesothelioma are caused by the actual build up associated fluid between the lining of your lung and the chest muscles cavity. The ailment may start inside chest region and pass on to other parts of the body. Other symptoms of pleural mesothelioma cancer include weight-loss, severe inhaling and exhaling trouble, temperature, difficulty swallowing, and bloating of the face and neck areas. It really should be noted that some people with the disease will not experience just about any serious indications at all. Deal Toys

Jackson 说:
2025年3月23日 22:19

This is a excellent website, could you be involved in doing an interview regarding just how you created it? If so e-mail me! Tombstones

Matthew Wade 说:
2025年3月24日 22:21

There are a couple of intriguing points at some point on this page but I do not determine if they all center to heart. There’s some validity but I will take hold opinion until I check into it further. Great post , thanks and then we want a lot more! Added onto FeedBurner too 온라인바카라

Jackson 说:
2025年3月31日 13:58

i like to search the internet for new kitchen gadgets to add to my kitchen. gate installation company


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee