Wizarding Duel (UVa Live Archive North Asia 2011 Amritapuri)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=519&page=show_problem&problem=3997

問題

N人で総当たり戦を行う。それぞれの人に対して整数aiが与えられる。それぞれの人の勝利数をbiとした時に、 $\min_{\left{b_1,b_2,\dots,b_N\right}\in{\cal B}}\sum_i |a_i - b_i|$ を求めよ。ただし、biを割り当てた時にそのような総当たり戦の結果を作ることが出来なければならない。
2<=N<=50
0<=ai<=100

解法

2部グラフの最大流で解く。片側の頂点群は各人に対応する。もう一方の頂点群は試合に対応し、N*(N-1)/2個の頂点がある。そして、srcから個人の頂点へ容量が勝利数の辺を張り、個人からその人が行った試合の頂点へ辺を張り、試合の頂点からdestへ辺を張る。このグラフ上での最大流の解をfとすると、答えは $\sum_{i=1}^N a_i + N * (N - 1) / 2 - 2 * f$ となる*1。

*1:fは何勝利分、aiに近づけることができるかの指標