MOBIVINA - MobiZone vs VinaGone
KTuan and AnhDQ, CEOs of two telecommunication corporations MobiZone and VinaGone have signed a contract to use their network in common. N people have accepted to try this new service. The ith people accepts to pay Mi to use MobiZone's service or Vi to use VinaGone's one; and any two people ith and jth accept to pay Cij in common whether they use different services (the network cost).
Find a way of choosing networks for N people satisfying the sum of total cost is minimum.
- The first line contains number N.
- The second line contains N number(s) Mi.
- The third line contains N number(s) Vi.
- The last N line(s), each of them contains N number(s) Cij (Cij = Cji).
- Contains the minimum total cost.
1 1 10
10 10 1
0 0 1
0 0 1
1 1 0
- N ≤ 250.
- The remaining numbers of Input do not exceed 1000.
Another similar problem: LightOJ 1361 - Component Placement
The last line of the statement means if two guys i and j use different services then they pay Cij (=Cji) once.
@Alex Abbas, I think the possible explanation is, you assign person1 with Mobi, person2 with Mobi and person3 with Vina. Then they need to pay 1 + 1 + 1 individually. Also, person1 and person3 are using different network, so they pay C more, same as person2 and person3, C more. totalling 3 + 1 + 1 = 5Last edit: 2013-09-19 05:40:15
I don't understand whether we need to connect all services to all people or just one service can u explain the input/output sample please...
The problem statement is unclear. Please rectify the grammar in the problem statement.