最近忙著預習課本備考,沒怎麼刷題,(我是真的有在好好看書。。)不敲題還是手癢癢,馬上就邀請賽了,還是每晚睡覺前都拿來刷題吧。白天的時間足夠了。
話說這題調了一晚上。。。一直以為是幾天沒敲狀態下滑。。(雖然也沒幾天。。)當發現錯誤的時候才發現原來是少敲了個字母。。。而且我一般很少在bfs的那個地方出錯,錯誤地方也很隱蔽。。所以找了一晚上,真是敲錯一個字母成千古恨。
這題大概是職業生涯目前為止敲得最長的一道算法題了。。(模擬題除外。。)先後用了二分(二分最大距離),求最短路(找機器與牛之間的最短距離),以及網絡流isap(判斷能否滿流,滿流說明此時所有牛都可以吃到食物)。
建圖思路是,建立一個超級源點與超級匯點,將機器與超級源點相連,權值為每台機器的最大供應量,將牛與超級匯點相連,權值為1,若牛與機器的最短距離小於等於二分到的最大距離,則連邊。權值為1.然後判斷是否滿流。每次二分都需要求一次最大流,並判斷是否滿流。最終的最小值就是所要求的答案。
代碼如下:
#include
#include
#include
#include
#include
#include
#include
#include