Houses and Restaurants

Problem code: RHOUSE

All submissions for this problem are available.

There is a city where people are fond of visiting restaurants. In fact, any building in this town is either a house or a restaurant. There are N buildings in the city and they are conveniently numerated by integer numbers from 1 to N. To move from some building to others there are M two-way roads. Each road connects two buildings. It is possible that there are several roads that connect the same pair of buildings, but there won't be a road that connects a building to itself. Chef wants to make the ways to his restaurants more interesting. To do that he is going to decorate some roads. Each road has its own integer cost of decorating. Some costs may be negative. If the cost is negative Chef will get some reward for decorating this road. Now Chef doesn't have much money so he wants to decorate roads in such a way that from each house, at least one restaurant is reachable using only decorated roads. The total cost of decorated roads should be minimal. So, your task is to help him to calculate the minimal cost of any satisfactory subset. It might be negative if Chef's rewards for decorating some roads are greater than his spent money.

Input

There first line of input contains an integer T - the number of test cases.
Then T test cases follow. For each test case there will be integers N and M - the number of buildings and the number of roads.
Then a string of N letter follows. I-th symbol of this string is "R" if the corresponding building is a restaurant and "H" if it is a house.
Then there are M lines. Each line consists of three integers - Xi Yi Zi. They describe a road that connects buildings Xi and Yi with the cost of decorating equal to Zi.

Output

For each test case output the minimal cost of any satisfactory subset of roads.

Constraints

2<=N<=100000
1<=M<=400000
-20000<=Zi<=20000
Sum over all N in a single input file will not exceed 200000.
Sum over all M in a single input file will not exceed 400000.
It is guaranteed that you can reach every building from any other building.
There is at least one resturant in the city.

Example

Input:

3
3 5
HHR
1 2 3
1 2 5
1 3 10
3 2 -1
3 1 7
2 2
RR
1 2 1
2 1 2
3 3
HRR
1 2 1
1 3 2
2 3 3

Output:
2
0
1

Author: xcwgf666
Date Added: 11-11-2011
Time Limit: 3 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

what is the constraint on T ?

k0stia @ 1 Jan 2012 09:01 PM
what is the constraint on T ?

T is not limited.

sergey_adm @ 1 Jan 2012 10:39 PM
T is not limited.

@segrey_adm : Can the total

ankush108 @ 1 Jan 2012 11:55 PM
@segrey_adm : Can the total cost of decoration of roads be negative ?

@ankush108 the problem

sergey_adm @ 2 Jan 2012 12:18 AM
@ankush108 the problem statement contains an answer to this question.

@sjaljain Please don't write

hiroto_adm @ 2 Jan 2012 02:33 AM
@sjaljain Please don't write about your algorithm. And I cannot give an answer for your question. Think it by yourself.

I think, this statement "from

fura2 @ 2 Jan 2012 02:37 AM
I think, this statement "from each house, at least one restaurant is reachable using only decorated roads" is ambiguous. There are 2 interpretations. (1) For any houses (say H), there exist at least one restaurant (say R) such that R is reachable from H using only decorated roads. That is, R may depend on H. (2) There exist at least one restaurant R such that R is reachable from all houses using only decorated roads. Which interpretation is correct?

@fura2 (1) is correct.

hiroto_adm @ 2 Jan 2012 02:55 AM
@fura2 (1) is correct.

does the satisfactory subset

calc_saransh @ 2 Jan 2012 12:57 PM
does the satisfactory subset need to be connected???

@calc_saransh the only

sergey_adm @ 2 Jan 2012 04:20 PM
@calc_saransh the only requirement is "at least one restaurant is reachable using only decorated roads" and it is described in the statement.

@wRabbits please, don't post

sergey_adm @ 2 Jan 2012 05:46 PM
@wRabbits please, don't post any test cases here. It comes obviously from the statement that any subset of decorated roads for which "at least one restaurant is reachable using only decorated roads" is OK. The task is to find the minimal possible cost of such subset.

Ok, thanks. I've had a pannic

wRabbits @ 2 Jan 2012 06:02 PM
Ok, thanks. I've had a pannic attack, so need to be sure about that. Of course it's obvious

@admin please can you explain

agarwalmanish @ 3 Jan 2012 05:38 PM
@admin please can you explain test case no.1 i mean how come the output comes 2..

@agarwalmanish please read

sergey_adm @ 3 Jan 2012 08:02 PM
@agarwalmanish please read the statement again carefully and think about it by yourself, if there are any ambiguities please indicate them @phantom11 please don't write here anything about your algorithm.

@phantom11 Please don't write

hiroto_adm @ 3 Jan 2012 08:23 PM
@phantom11 Please don't write additional test cases. The minimum cost can be negative (that is indicated and defined in the problem statement), and min(-1, 0) = -1.

i think there is a major

cyberax @ 4 Jan 2012 01:10 AM
i think there is a major ambiguity here. as cycles in the graph are allowed by definition, and as negative-weighted edges are permitted as well, some situations lead to a path from an H to a R with a weight = -infinity. what is the expected answer in that kind of configuration ?

any other test cases anyone

sehrawat.parshant @ 4 Jan 2012 01:41 AM
any other test cases anyone

i think there is a problem

udit1992 @ 4 Jan 2012 08:18 AM
i think there is a problem with the server. When i am submitting my solution for this problem , it is showing some errors regarding the language field.

@anujkaliaiitd You cannot ask

hiroto_adm @ 4 Jan 2012 10:26 AM
@anujkaliaiitd You cannot ask for help in the contest. Please solve by yourself.

@cyberax Read problem

hiroto_adm @ 4 Jan 2012 10:28 AM
@cyberax Read problem statement carefully. You may misunderstand.

@sehrawat.parshant Don't

hiroto_adm @ 4 Jan 2012 10:29 AM
@sehrawat.parshant Don't require more test cases. I think you can generate more test cases if needed.

@hiroto_adm: thank you. you

cyberax @ 4 Jan 2012 05:42 PM
@hiroto_adm: thank you. you made me understand my mistake. it's not a problem about finding minimum weight of a path, but the minimum decoration cost needed to satisfy the constraints. i didn't understand that very well, as english is not my native language. :)

@hiroto_adm: my solution is

sehrawat.parshant @ 5 Jan 2012 10:24 PM
@hiroto_adm: my solution is working for test cases i produced and given test cases, but online judge is showing WA. can you please provide me some more test cases.

@sehrawat.parshant you can

sergey_adm @ 6 Jan 2012 02:49 AM
@sehrawat.parshant you can not ask for any help with the solutions or the test cases during the competiton. Please, think the test cases over yourself.

@admin: If there is one house

login_test @ 6 Jan 2012 08:57 AM
@admin: If there is one house and one restaurant connected by two roads of costs -5 and -10, answer would be -10 or -15 ??

@login_test: read the problem

cyberax @ 7 Jan 2012 12:54 AM
@login_test: read the problem statement : "So, your task is to help him to calculate the minimal cost of any satisfactory subset."

if two roads can have same

assasin143 @ 7 Jan 2012 11:49 AM
if two roads can have same cost??

@assasin143 Read the problem

hiroto_adm @ 7 Jan 2012 02:30 PM
@assasin143 Read the problem statement carefully.

@swaprocks123 there is an

sergey_adm @ 7 Jan 2012 06:38 PM
@swaprocks123 there is an answer to your question in the problem statement.

can any one plz tel me the

cool123 @ 10 Jan 2012 08:57 PM
can any one plz tel me the limit for N? I m getting run time error. n<=100000 assertion is failing. Plz reply.

Plz reply admin

cool123 @ 10 Jan 2012 09:33 PM
Plz reply admin

@cool123 Please read the

hiroto_adm @ 11 Jan 2012 12:42 AM
@cool123 Please read the problem statement, and check your code.

@admin: N <= 100000 . Am I

cool123 @ 11 Jan 2012 08:02 AM
@admin: N <= 100000 . Am I correct admin? This assertion is failing. Plz reply.

@cool123 The test data is

sergey_adm @ 11 Jan 2012 12:34 PM
@cool123 The test data is correct. I can't help you with finding the mistake in your code during the competiton. Please, don't panic.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions