P3544 [POI 2012] BEZ-Minimalist Security

A map of Mafiatown's road network is given. The network consists of intersections and bidirectional streets that connect them. The streets cross only at the intersections, but they may lead through tunnels or flyovers. Each pair of intersections is linked by at most one street. At every intersection $v$ there is a police station manned by $p(v)$ policemen. A street linking the intersections $u$ and $v$ is considered safe if there are at least $b(u,v)$ policemen in total in the two stations at the streets ends. Initially $p(u)+p(v)\ge b(u,v)$ holds for every street. However, due to an ongoing crisis the mayor Byteasar has ordained the Minimalist Security Act (MSA), which states that: a certain number (which may be zero) of policemen is to be laid off from each police station (we denote the number of policemen laid off from the station at the intersection $v$ by $z(v)$), after the layoff, the total number of the policemen at both ends of every street connecting some two intersections, say $u$ and $v$, should equal $b(u,v)$ exactly, i.e.: $p(u)-z(u)+p(v)-z(v)=b(u,v)$ These rules do not determine uniquely how many policemen are to be laid off. Byteasar wonders what is the minimum and the maximum number of laid off policemen (the sum of $z$ values over all intersections) that complies with aforementioned rules.

N/A

N/A