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.
Input
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.
Output
MaximumProfit [other tests]
Example
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.
hide comments
joqsan_77:
2018-08-28 11:02:50
Nice one.
|
|
Pankaj Jindal:
2013-12-09 11:25:42
Try thinking of a flow scenario in a bipartite graph. Then use Dinic's algorithm, its pretty fast in case of bipartite graphs. |
|
Brian Bi:
2009-03-25 02:23:24
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 |
|
李同叔:
2009-03-20 02:02:10
I would like to ask: how many test cases are there? |
|
李同叔:
2009-03-19 23:39:56
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 |
Added by: | Fudan University Problem Setters |
Date: | 2007-04-01 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: C99 ERL JS-RHINO |
Resource: | Chinese National Olympiad in Informatics 2006,Day 2; translated by Blue Mary |