PROFIT - Maximum Profit
CS&T, the well-known cellphone company, is going to set some new service stations among n possible ones, which are numbered 1,2,...,n. The costs of setting these stations are known as P1,P2,..,Pn. Also the company has made a survey among the cellphone users, and now they know that there are m user groups numbered 1,2,...,m, which will communicate by service station Ai and Bi, and the company can profit Ci.
Now CS&T wants to know which service stations are to be set that the company will profit most.
T [The number of tests] n m [n<=5000 m<=50000] P1 P2 P3 ... Pn [Pi<=100] A1 B1 C1 A2 B2 C2 ... Am Bm Cm [1<=Ai,Bi<=n, Ci<=100] [other tests]
At least 80% of the tests satisfy that n<=200, m<=1000.
MaximumProfit [other tests]
Input: 1 5 5 1 2 3 4 5 1 2 3 2 3 4 1 3 3 1 4 2 4 5 3 Output: 4 Hints: The service stations to be set are 1,2,3.
Try thinking of a flow scenario in a bipartite graph. Then use Dinic's algorithm, its pretty fast in case of bipartite graphs.
Try the Improved Shortest Augmenting Path Algorithm at TopCoder. (Disclaimer: I don't know if it actually works or not.)Last edit: 2010-05-05 20:36:12
I would like to ask: how many test cases are there?
I am currently using the Ford Fulkerson algorithm for calculating the max flow of the graph. However, since there are lots of nodes, the algorithm is too slow. Could anyone suggest a faster algorithm to find the max flow? Thanks.Last edit: 2009-03-19 23:39:56