HackerEarth Quantitative coefficient problem solution

In this HackerEarth Quantitative coefficient problem solution It is very important to understand relationship between variables to draw the right conclusion from a statistical analysis. The relationship between variables determines how the right conclusions are reached. Without an understanding of this, you can fall into many pitfalls that accompany statistical analysis and infer wrong results from your data.

Linear programming (LP; also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints.

We are not going to present some LP theory, but let’s have a look at combinatorial problem related to this theory. Suppose you have a set of N variables. There are M relationships of some pairs of these variables. More formally, you have M relationships of type ai, bi, ci which means that variables ai and bi are in a relationship with quantitative coefficient ci. Quantitative coefficient of a connected set S of variables is a product of all relationship quantitative coefficients in this set.

Set S of variables is called connected if any two variables in this set are connected. Variables x and y are called connected if at least one of the following conditions is satisfied:

x and y are put in relationship directly
there is such a variable z that x and z are connected and y and z are connected too.

You are given a connected set S of N variables and M relationships. Your task is to leave some of these relationships in such a way that S is still connected and its quantitative coefficient is minimal possible.

HackerEarth Quantitative coefficient problem solution.

#include <bits/stdc++.h>
#define bs 1000000007

using namespace std;

int n,m,tests,a[1<<20],b[1<<20],c[1<<20],w[1<<20];

int ans;

int get(int x)
{
  if (x==w[x])
    return x;
  return w[x]=get(w[x]);
}

void merge(int a,int b)
{
  w[a]=b;
}

vector<pair<int, int> > v;

int main(){
ios_base::sync_with_stdio(0);
//cin.tie(0);

cin>>tests;
for (;tests;--tests)
{
  cin>>n>>m;
  v.clear();
  for (int i=1;i<=m;i++)
  {
    cin>>a[i]>>b[i]>>c[i];
    v.push_back(make_pair(c[i],i));
  }
  ans=1;
  sort(v.begin(),v.end());
  for (int i=1;i<=n;i++)
    w[i]=i;
  for (int i=0;i<v.size();i++)
  {
    int id=v[i].second;
    int ta,tb;
    ta=a[id];
    tb=b[id];
    ta=get(ta);
    tb=get(tb);
    if (ta==tb)
      continue;
    ans=1ll*ans*c[id]%bs;
    merge(ta,tb);
  }
  cout<<ans<<endl;
}

return 0;}

coding problems solutions