网络流建模汇总
?前言
最近在看?Edelweiss 的網絡流建模匯總
來學習網絡流的建模技巧
畢竟網絡流的題難點就在于如何建圖，其余大部分就是套路了
于是也寫下自己的想法和思路
(雖然一直在借鑒大佬思路)
?最大流
?POJ 1149 ?Pigs
【題目大意】
有 M 個豬圈，每個豬圈里初始時有若干頭豬pig[i]。一開始所有豬圈都是關閉的。依次來了 N 個顧客，每個顧客分別會打開指定的幾個豬圈，從中買若干頭豬。每 個顧客分別都有他能夠買的數(shù)量的上限。每個顧客走后，他打開的那些豬圈中的 豬，都可以被任意地調換到其它開著的豬圈里，然后所有豬圈重新關上。問總共 最多能賣出多少頭豬。（1 <= N <= 100, 1 <= M <= 1000）
【思路】
設一個s點為源點，一個t點為匯點
每來一個顧客$m+i$(顧客從m+1開始編號)，如果他所擁有鑰匙的豬圈還未被打開過，那連一條源點和他 流量為此豬圈的豬的數(shù)量$(s,i,pig[i])$的邊
如果他所擁有鑰匙的豬圈$index$被打開過，那連一條前一個打開的人和他 流量為INF的邊$(vis[index],i,INF)$
每個顧客與匯點連一條流量為此顧客購買力的邊$(m+i,t,buy)$
其實就是把可以調換的豬圈混合在了一起，s-t流和調換豬對應了起來
【樣例】
3 3
3 1 10
2 1 2 2
2 1 3 3
1 2 3
7
【代碼】
POJ 1149 Pigs
?POJ 3281 ?Dining
【題目大意】
有 F 種食物和 D 種飲料，每種食物或飲料只能供一頭牛享用，且每頭牛只享用一 種食物和一種飲料。現(xiàn)在有 N 頭牛，每頭牛都有自己喜歡的食物種類列表和飲 料種類列表，問最多能使幾頭牛同時享用到自己喜歡的食物和飲料。（ 1 <= F <= 100, 1 <= D <= 100, 1 <= N <= 100）
【思路】
以往一般都是左邊一個點集表示供應并與源相連， 右邊一個點集表示需求并與匯相連。現(xiàn)在不同了，供應有兩種資源，需求仍只有 一個群體，
根據(jù)這個群體與兩種資源的聯(lián)系來看，食物和飲料之間并沒有直接聯(lián)系，而是牛與食物，牛與飲料分別有聯(lián)系
可以把牛放在兩種資源中間，源點與食物相連，飲料與匯點相連，然后牛在中間食物與牛相連 牛與飲料相連（t->食物->牛->飲料->匯點）
但是會出現(xiàn)一只牛吃多種食物多種飲料的情況所以要把牛拆點拆成（牛，牛'，1）為了保證只能吃一次，兩者之間流量為1
【樣例】
4?3?3
2?2?1?2?3?1
2?2?2?3?1?2
2?2?1?3?1?2
2?1?1?3?3
3
->
?一只牛會吃多個套餐 一只牛只能吃一個套餐
【代碼】
POJ 3281 Dining?
?JOJ 2453? Candy
【題目大意】
有$N$顆糖果和$M$個小孩，老師現(xiàn)在要把這$N$顆糖分給這$M$個小孩。每個小孩$i$對每顆糖$j$都有一個偏愛度$A_{ij}$，如果他喜歡這顆糖$A_{ij} = 2$，否則 $A_{ij} = 1$。小孩$i$覺得高興當且僅當$∑C_{ij}×A_{ij} >= B_{i}，j=1,2,…,N$，若他分得了糖 $j$,$C_{ij} = 1$否則$C_{ij} = 0$。問能否合理分配這$N$顆糖，使得每個小孩都覺得高興。（$1 <= N <= 100,000$, $1 <= M <= 10, 0 <= B_{i} <= 1,000,000,000$）
【思路】
一種最直觀的想法就是每顆糖 i 作為一個點并連邊(s, i, ?)，每個小孩 j 作為一個 點并連邊(j, t, Bj)。若小孩 j 喜歡糖果 i 則連邊(i, j, 2)，否則連邊(i, j, 1)，然后求一 次最大流看是否等于∑Bj，但是源點和糖之間的流量無法確定，為什么呢？因為一旦選定一條邊之后就只能從這條邊流而不能再進入其他的出邊
假設流量為1，那如果小孩喜歡此糖的話，流量需要為2，所以pass!
假設流量為2，如果小孩不喜歡的話，流量需要為1，且不能再流向其他小孩了，為2的話就不能保證不再流量另一個不喜歡的小孩，所以pass!
現(xiàn)在轉換一下思路，由于問的是否所有孩子都能高興，為了盡量讓孩子高興，所以每顆糖都會分出去,即$C_{ij} = 1$
假設有$x$個$A_{ij}=2$,其余$A_{ij}=1$，則?$∑C_{ij}×A_{ij} =∑1*A_{ij}=N+x$，則所有小孩都高興即為$N+x>=∑B$j
所以只考慮可以額外提供1點高興值的糖果和小孩，因為貢獻值從2變?yōu)?減半了，所以小孩到匯點的流量也需要減半，
(達到快樂就行了 不能讓他多吃了糖果 還有其他小孩呢)
?這樣就只需要判斷小孩是不是喜歡這塊糖了，如果喜歡的話，就連邊流量為1，如果不喜歡的話就不連邊，或者流量為0也行
【樣例】
1
4?3
1?2?1
2?1?1
1?1?2
1?2?2
3?2?2
1?1
YES
【代碼】
JOJ 2453?Candy
?ZOJ 2760? How Many Shortest Path
【題目大意】
給定一個帶權有向圖 G=(V, E)和源點 s、匯點 t，問 s-t 邊不相交最短路最多有幾 條。（1 <= N <= 100）
【思路】
分別以源點和匯點為起點跑dijkstra，得到最短路圖，令最短路的邊流量都為1，在最短路上跑最大流，得到獨立路徑條數(shù)
類似于hdu 6852，不過最短路圖加邊時令流量為1
?WOJ 1124? Football Coach
【題目大意】
有 N 支球隊，互相之間已經進行了一些比賽，還剩下 M 場沒有比。現(xiàn)在給出各 支球隊目前的總分以及還剩下哪 M 場沒有比，問能否合理安排這 M 場比賽的結 果，使得第 N 支球隊最后的總分大于其他任何一支球隊的總分。已知每場比賽 勝者得 2 分，敗者 0 分，平局則各得 1 分。（1 <= N <= 100, 0 <= M <= 1000）
【思路】
?首先利用貪心的思想，讓第N支球隊贏剩下的所有他參加的比賽，如果此時仍有球隊的總分大于等于球隊 N 的總分$score[N]$，則已經不可能滿足要求；
如果滿足的話，想要N贏，那其他的球隊i的得分肯定比$score[N]$小，對于除與N以外球隊來說，設現(xiàn)在第i支球隊得分為$score[i]$,所有比賽結束后得分為$score[i']$
即$score[i']<score[N]$,$score[i']$最大為$score[N]-1$,所以最多再贏$score[N]-score[i]-1$分,也就是每支球隊到匯點的容量為$score[N]-score[i]-1$
對于除與N相關以外的比賽來說，源點到比賽j的容量為2,(s,j,2),每場比賽向與其關聯(lián)的兩支球隊 u, v 連邊(j, u, 2), (j, v, 2)
【樣例】
5?4
4?4?1?0?3
1?3
2?3
3?4
4?5
NO
?SGU 326? Perspective
【題目大意】
NBA 某小組內有 N 支球隊，小組內以及小組間已經進行了若干場比賽。現(xiàn)在給 出這 N 支球隊目前勝利的場數(shù)、還剩多少場沒有比（包括小組內和小組間）以 及小組內任意兩支球隊之間還剩多少場沒有比，問能否合理安排剩下的所有比賽， 使得球隊 1 最后成為小組冠軍或者并列冠軍。 （2 <= N <= 20, 0 <= x <= 10000, x 表示其他任何輸入）?
【思路】
跟上面WOJ 1124? Football Coach差不多，先令與球隊1相關的賽事都讓球隊1贏，由于想讓1贏，那么應該盡可能加大其他隊與1的差距 ，
所以令除1以外的小組間的賽事都輸，注意這個是可以并列，所以每支球隊到匯點的容量為$score[N]-score[i]$
所有小組內的比賽 i（不包括與球隊 1 相關的比賽）作為一個點并加邊$(s, i, num[i])$，每支球隊（不包括球隊 1）作為一個點并加邊$(j, t, score[N]-score[i])$，每場 比賽向與其關聯(lián)的兩支球隊 u, v 連邊$(i, u, ∞), (i, v, ∞)$。至于其他球隊小組間的 比賽，直接讓他們輸?shù)艟秃?#xff0c;不用管。若最大流等于$∑num[i]$則可以滿足要求。
?SPOJ 287? Smart Network Administrator
【題目大意】
一座村莊有 N 戶人家。只有第一家可以連上互聯(lián)網，其他人家要想上網必須拉 一根纜線通過若干條街道連到第一家。每一根完整的纜線只能有一種顏色。網管 有一個要求，各條街道內不同人家的纜線必須不同色，且總的不同顏色種數(shù)最小。 求在指定的 K 戶人家都能上網的前提下，最小的不同顏色種數(shù)。（1 <= N <= 500）
【思路】
以第一家作為匯點 t，K 戶人家中的每一戶 i 作為一個點并連邊$(s, i, 1)$，對每條街道$(u, v)$，連邊$(u, v, c), (v, u, c)，c=∞$。 這樣求完最大流后每一條 s-t 流均對應一戶人家的纜線，而各條街道內的流量表 示有多少戶人家的纜線同時穿過該街道，那么這個流量就是只考慮該條街道的時候最少的不同顏色種數(shù)。那么答案是否就是所有街道的不同顏色種數(shù)的最大值呢？ 當然不是！最大流只保證總流量最大，而不會去管每條流具體該往哪兒流，所以 這么做不一定能得到最優(yōu)解。我們只要稍微修改這個模型就一定能保證得到最優(yōu) 解：去對c進行二分，強制 c 等于某個值 limit，再對網絡求最大流，如果等于 K，說明用 c 種不同 的顏色已經足夠了；如果小于 K，說明 c 種還不夠，還需要往高了調。同時此處 的單調性也很明顯：c 越高越容易滿足要求。
【樣例】
5?5?4
2?3?4?5
1?2
1?3
2?3
2?4
3?5
4
?一種顏色代表一根線，同一根線n種顏色代表流量為n
?SPOJ 962? Intergalactic Map
【題目大意】
在一個無向圖中，一個人要從 1 點趕往 2 點，之后再趕往 3 點，且要求中途不 能多次經過同一個點。問是否存在這樣的路線。（3 <= N <= 30011, 1 <= M <= 50011）
【思路】
由于是從1到2,再從2到3，可以看做是從2到1,從2到3有沒有獨立的路徑，沒有重合的點
為了保持點不重合，我們可以把i點拆開連邊$(i,i',1)$，其中$i$點為入點，$i'$點為出點
以2的出點為源點，以0為匯點，為了必須經過1,3點，對1和3的出點和匯點連邊$(1',t,1),(3',t,1)$
對于輸入的邊$(u,v)$，利用入點和出點的關系連接即$(u',v,1),(v',u,1)$
然后判斷從源點到匯點的路徑是否是兩條
最后 輸入的時候，可能有邊不在1~n的范圍內，需要跳過這些邊。
【代碼】
?spoj?Intergalactic Map
?
?
?
?
轉載于:https://www.cnblogs.com/MMMinoz/p/11615033.html
總結
- 上一篇： [视频教程] 使用composer安装使
- 下一篇： CodeForces Goodbye