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