Connection Status:
Competition Arena > MinMaxMax

MinMaxMax

SRM 710 · 2017-02-20 · by lg5293

SRM 710 · 2017-02-20 · by lg5293 · Graph Theory
Class Name: MinMaxMax
Return Type: long
Method Name: findMin
Arg Types: (vector<int>, vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

You are given an undirected graph with n nodes and m edges. The nodes are labeled from 0 to n-1. This graph is guaranteed to be connected and have no self-loops or multiple edges.

You are given a description of the graph: the int[]s a, b, w, and v. For each valid i, there is an edge that connects nodes a[i] and b[i] and has weight w[i]. For each valid j, node j has weight v[j]. All weights are positive integers.

A path in this graph is a sequence of pairwise distinct nodes such that each pair of consecutive nodes is connected by an edge. The difficulty of a path is the value (N times E), where N is the maximum weight of a node on the path (including the nodes where it starts and ends) and E is the maximum weight of an edge on the path.

For each pair of distinct nodes i and j, let d(i,j) be the smallest possible difficulty of a path that connects i and j. Find and return the sum of d(i,j) with 0 ≤ i < j ≤ n-1.

Notes

  • The values of n and m are not explicitly given. n can be inferred from the length of v and m can be inferred from the length of w.

Constraints

  • n will be between 2 and 300, inclusive.
  • m will be between n-1 and min(2,500, n choose 2), inclusive.
  • a,b,w will contain exactly m elements.
  • It is guaranteed that the graph described by a,b is connected and has no self loops or multiple edges.
  • Each element of w will be between 1 and 10^6, inclusive.
  • v will contain exactly n elements.
  • Each element of v will be between 1 and 10^6, inclusive.
Examples
0)
{0}
{1}
{5}
{3,6}
Returns: 30

There are two nodes and a single edge in this graph. Node 0 has weight 3 and node 1 has weight 6. There is an edge between node 0 and node 1 with weight 5. In this case we just want to find d(0,1). This is equal to 5*6=30.

1)
{0,0,1}
{1,2,2}
{10,11,12}
{6,5,4}
Returns: 186

We have the following values: d(0,1)=60 d(0,2)=66 d(1,2)=60

2)
{0,0,1}
{1,2,2}
{100,1,1}
{1,1,100}
Returns: 300

In this case each d(i,j) is 100. For example, consider d(0,1). There are two possible paths. The path 0-1 has maximum node weight 1 and maximum edge weight 100, hence its difficulty is 1*100 = 100. The path 0-2-1 has maximum node weight 100 and maximum edge weight 1, hence its difficulty is 100*1 = 100 as well.

3)
{0,1,2,3,4,5,6,7,8,9}
{1,2,3,4,5,6,7,8,9,10}
{1000000,1,1000000,1,1000000,1,1000000,1,1000000,1}
{1000000,1,1000000,1,1000000,1,1000000,1,1000000,1,1000000}
Returns: 50000005000000

Watch out for overflow

4)
{9,12,4,11,0,8,6,11,11,10,12,7,3,12,3,10,0,3,2,7,
0,10,8,1,11,9,2,0,3,6,4,2,3,5,9,0,6}
{0,5,6,5,10,2,1,2,3,4,6,9,9,10,5,5,6,4,12,5,12,7,
7,3,4,12,4,1,8,7,1,6,6,4,11,5,11}
{879651,656980,11,51564,206,420,917584,205,59290,3323,
644,1,13243,84162,154,561242,1,190,10,136901,420623,
353,573129,81,25,133670,72,528049,5,715560,82641,46,
1,527672,923948,1,13}
{5,1829,51302,3026,4,14,5189,3,25289,2,2967,15994,6}
Returns: 157740289

Submissions are judged against all 64 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MinMaxMax with a public method long long findMin(vector<int> a, vector<int> b, vector<int> w, vector<int> v) · 64 test cases · 2 s / 256 MB per case

Submitting as anonymous