Repository contains project of "Graph algorithms" course at AHG UST in Cracow. Algorithm solving microbribery problem implemented with c++.
King is organizing an chess tournament in order to win in. He introduced following rules. Every two players plays against. Winner is the player with most wins except draw, then king is the winner. Chess game isn't king's strong site so he need to cheat. King servants, based on previous analysis, know each duel result. They can bribe players to change result of single duel. Each bribery cost a specific amount of money. The point is to mineralize cost of briberies and let the king win.
More detailed description here
The input file in the first line contains a T that tells how many tournament problems solve. The ist of lines contains tournament description in the following formats:
- B - tournament organizer's budget
- n - number of tournament participants. King has 0 number.
- In next n*(n-1)/2 lines there are four numbers x,y,w,b meaning x play against y, w player who wins, b cost of microbribery
Example:
Output file contains T lines
- TAK - if king can afford bribery
- NIE - else
Solved using modified maxflow mincost algorithm.
Picture source : Journal of Artificial Intelligence Research 35 (2009) 275-341 Llull and Copeland Voting Computationally Resist Bribery and Constructive Control