PROFIT - Maximum Profit

no tags 

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.

Try to frame it as a Min-Cut problem.

Last edit: 2018-08-28 11:03:19
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