網(wǎng)絡(luò)流
題目描述：已知之前的一些比賽雙方和結(jié)果，和未來的賽事安排，問DD能否奪冠，不能并列
我們談心的讓未來DD參加的比賽都贏，且我們可以知道未來每個人最多可以贏幾場
給所有選手編號，預(yù)先統(tǒng)計出所有選手已經(jīng)勝利的場次，然后對所有還沒有進行的比賽，假設(shè)其中任意一個選手獲勝，并統(tǒng)計勝負關(guān)系，（加入每個人勝利的次數(shù)在w[]中，每兩個選手互相對戰(zhàn)勝利的次數(shù)在a[][]中）即某兩個選手a,b進行比賽a贏b的次數(shù)和b贏a的次數(shù)，這里要注意的是兩個選手進行比賽，你假設(shè)任意一個選手獲勝都是正確的，待會你會發(fā)現(xiàn)其實假設(shè)僅僅只是假設(shè)。增加超級源超級匯，超級源向每一個結(jié)點射出一條容量是這個點勝利場次的邊，所有的點向匯點連一條容量是w[ID[DD]]-1的邊，顯然是為了限制每個點的勝利次數(shù)不能大于等于DD.中間任意兩個結(jié)點根據(jù)勝負關(guān)系建立一條容量是a[i][j]的邊，跑一遍最大流即可，如果滿流，說明有可行解，否則無解。
下面來分析一下構(gòu)圖的原理，超級源向所有選手連一條容量是他將要獲勝場次的邊，比如說是c，說明這個選手有c場勝利要分配，如果這條邊上的流量直接流向了匯點，說明該選手獲勝，如果流量通過有向邊流向了他的對手，說明這個勝利果實被他的對手拿走了，也就是實際上輸?shù)袅吮荣悾晕也耪f假設(shè)僅僅是假設(shè)。再加上有每個點到匯點的限流，跑一遍最大流如果能滿流說明比賽可以合理的分配勝負關(guān)系使得每個人的勝利場次都不超過DD,如果不能，無解。
這題構(gòu)圖確實很精彩，贊！