Maximum Wins on the Main Tree

ID: 16952

Type: Default

1000ms

256MiB

A magical tree bears five types of individuals. The five types are:

J ("主主")
HK ("记记")
W ("高高")
E ("王王")
YYY ("歪歪")

There are exactly N people of each type on the tree. Two persons of different types can battle (persons of the same type cannot battle). The outcome of a battle is predetermined by the following rule. Represent the five types as numbers by

J=0,\; HK=1,\; W=2,\; E=3,\; YYY=4.

Given two different types a and b, let the difference be computed modulo 5 as $$d=(b-a)\bmod5.$$ If d=1 or d=2 then the person of type a wins; otherwise (i.e. if d=3 or d=4) the person of type b wins.

The tree's inhabitants have a life value measured in seconds. When an individual participates in a battle, its life decreases by 1. An individual whose life reaches 0 cannot battle further except the following special rule:

If an individual of type $J$ has its life drop to 0, any individual of type $YYY$ on the tree can donate 1 second to that particular $J$. However, each $YYY$ can donate at most once to each $J$. Thus every $J$'s effective battle capacity is increased by up to $N$ (since there are exactly $N$ individuals of type $YYY$).

byx and Shino-chan (诗乃酱) will organize M battles. In every battle, they select two distinct individuals from the tree to fight. They are free to choose the pair and to decide which one of the two will represent byx. A battle counts as a win for byx if the pre‐determined outcome (based on the rule above) favors the person designated for byx.

Each battle consumes 1 life from each participant. Note that any given pair of individuals may battle at most once. Your task is to determine the maximum number of battles byx can win by scheduling the battles optimally.

Modeling as a Flow Problem

We can view the problem as a resource allocation problem. For every type, an individual can participate in a number of battles equal to its life. For type $J$, the effective number of battles is increased by donation. In particular, if an individual of type $J$ has initial life $L$, its effective capacity is $L+N$ (since there are $N$ potential donations available).

There is a fixed winning relation. The winning matchups are as follows (note that in any battle the two individuals must be of different types):

$J$ wins against $HK$ and $W$.
$HK$ wins against $W$ and $E$.
$W$ wins against $E$ and $YYY$.
$E$ wins against $YYY$ and $J$.
$YYY$ wins against $J$ and $HK$.

The idea is to use an individual as the winner from one of the groups and to sacrifice an opponent from a group that loses to it. Let the winner supply for each group be the sum of the life values of its individuals (and for group $J$ add an extra $N$ per individual). Similarly, the loser capacity for a group is simply the sum of the life values of its individuals. Then for every allowed winning matchup (from group i to group j such that type i wins over type j), we can set up an edge in a flow network.

Construct a bipartite graph with the 5 groups as winners on the left and the same 5 groups as losers on the right. For group $i$ the supply is defined as:

If $i$ is $J$ (type 0): $S_0=\text{sum}(L_J)+N\times N$.
Otherwise: $S_i=\text{sum}(L_{\text{group }i})$.

For a losing group, the capacity is just the sum of the life values (no donation bonus). Then add an edge from the source to each winner-group with capacity equal to its supply, an edge from each loser-group to the sink with capacity equal to its capacity, and for every allowed winning matchup (from group $i$ to group $j$) add an edge from winner-group $i$ to loser-group $j$ with a large capacity.

The maximum flow in this network gives the maximum number of winning battles that can be scheduled. However, only M battles are held. Thus, the answer is the minimum of M and the maximum flow.

Input and Scheduling:

The input is given in 6 lines. The first line contains two integers $N$ and $M$ ($1 \le N \le 100$, $1 \le M \le 1000$). The next 5 lines each describe one type in the order: $J$, $HK$, $W$, $E$, $YYY$. Each of these lines contains $N$ integers representing the life values (at most 50) of the individuals of that type.

Input Format Summary

N M
L_{J1} L_{J2} ... L_{JN}
L_{HK1} L_{HK2} ... L_{HKN}
L_{W1} L_{W2} ... L_{WN}
L_{E1} L_{E2} ... L_{EN}
L_{YYY1} L_{YYY2} ... L_{YYYN}

Output Format

Output a single integer, the maximum number of battles byx can win.

inputFormat

The first line contains two integers $N$ and $M$. Each of the next five lines contains $N$ space‐separated integers. The five lines correspond to types $J$, $HK$, $W$, $E$, $YYY$ respectively.

N M
L_{J1} L_{J2} ... L_{JN}
L_{HK1} L_{HK2} ... L_{HKN}
L_{W1} L_{W2} ... L_{WN}
L_{E1} L_{E2} ... L_{EN}
L_{YYY1} L_{YYY2} ... L_{YYYN}

outputFormat

Output a single integer: the maximum number of battles byx can win.

sample

#P3701. Maximum Wins on the Main Tree

Maximum Wins on the Main Tree