志愿者招募

題目鏈接

https://www.luogu.org/problemnew/show/P3980

題解

這道題很神奇,這種建圖方法很有啟發性.

我們平時做的題都點都是是一對一的,而這道題的點的對應關系是一對多(即一個志愿者對應一段連續的區間,也就是多個時間點)的,直接按照傳統的網絡流建圖方法來做是不可行的.因此,我們考慮轉化一下思維.

考慮從原點出發的一個流量代表一個志愿者,那么一個志愿者可以連續干一段區間意味著這個流量可以跨過一段時間點.因此一個志愿者可以表示為$s_i\to t_i+1$的一條容量為$inf$,費用為$c_i$的邊.

第$i\to i+1$天,我們連接一條容量為$INF?a_i$,費用為$0$的邊,表示的是免費的志愿者.

這樣優先會流的時候會優先選擇這樣的邊流過去,當流量不足的時候,會選擇從有費用的邊流,表示增添志愿者.

總結

以上是生活随笔為你收集整理的P3980 NOI2008志愿者招募的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。