Estate Agent
Time limit2sMemory limit512 MB
Given directed offers between families with amounts, pick a subset of disjoint cycles so the total sum of offer amounts is maximized, then output 5% of it.
- Level
Hard8 of 10
- Topics
- Graph, Dynamic programming, Combinatorics, Implementation
- Solved
- No attempts yet
Problem
Rupert makes a living as the only real estate agent in a small town in England. He asks for 5% commission for every house that he sells.
Rupert organises one big auction per year. Every family (numbered from 1 to n) must take part in this auction, although making or accepting an offer is optional. Everyone bids for the houses they would like to move to, provided they can sell their current house at the same time.
This is a very transparent process: Rupert can see exactly how much commission he will make if he accepts the right buyers' offers on behalf of the sellers. He may discard some offers from buyers in order to drive up the overall commission. In fact, he might even decide to discard all of the offers from one family and let them stay in their current home, if it makes more money for him.
Find the maximum commission Rupert can make if he discards offers optimally.
Input
The input consists of:
- one line containing two integers n and m (1 ≤ n ≤ 150, 0 ≤ m ≤ n × (n − 1)), the number of families on the market and the number of offers made.
- m lines describing the offers. The ith such line contains three integers fi, hi and ai (1 ≤ fi, hi ≤ n, fi ≠ hi, 0 ≤ ai ≤ 10^6), the family making the offer, the family that owns the house the offer is for and the amount offered. No family makes more than one offer to the same house.
Output
Output how much Rupert will earn via commissions if he discards offers optimally. Your answer must be accurate to an absolute or relative error of 10^−6.