PROFIT  Maximum Profit
CS&T, the wellknown 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:
20180828 11:02:50
Nice one.


Pankaj Jindal:
20131209 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:
20090325 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: 20100505 20:36:12 

李同叔:
20090320 02:02:10
I would like to ask: how many test cases are there? 

李同叔:
20090319 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: 20090319 23:39:56 
Added by:  Fudan University Problem Setters 
Date:  20070401 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: C99 ERL JSRHINO 
Resource:  Chinese National Olympiad in Informatics 2006,Day 2; translated by Blue Mary 