Friends :
Difficulty Level : Medium
Submissions : 906
Asked In :
Marks :30
: 16 | : 2
Given $$$N$$$ people. For a pair of people, they have a friend value $$$A[i][j]$$$. We want to split these people into $$$N$$$ groups, such that each people belong to exactly one group and each group contains at least one person. The partition value of a split is defined as the minimum friend value over all the pairs of different people within the same group. Find the maximum partition value possible.
Suppose the minimum friend value of all pairs of different people from $$$Group1$$$ is $$$min1$$$ and from $$$Group2$$$ is $$$min2$$$. Then the partition value is defined as $$$min(min1,min2).$$$
The first line contains an integer $$$N$$$ representing the number of people. The next $$$N$$$ line contains $$$N$$$ integers where $$$A[i][j]$$$ represents the friend value between $$$A[i][j].$$$$$$(3 \le N \le 500)$$$,$$$(1 \le A[i][j] \le 10^9)$$$,$$$(A[i][i]=0)$$$,$$$(A[i][j]=A[j][i]).$$$
4 0 1 2 3 1 0 4 5 2 4 0 9 3 5 9 0
3
4 0 702209411 496813081 673102149 702209411 0 561219907 730593611 496813081 561219907 0 814024114 673102149 730593611 814024114 0
702209411
