HackerEarth Encounter with the Lord problem solution

In this HackerEarth Encounter with the Lord problem solution Crossing all the hurdles, Gudi now reaches the roof of the castle and she finds Puchi, the Lord of Azkahar and the Protector of the castle, waiting for her. After having been through the stages in the castle, Gudi has had a change of heart and no longer wants the treasure. Instead, she expresses her desire to become the Lady of Azkahar. However, the position of the Lady can not be won that easily. Puchi decides to take a final test.

He weaves his magic and N Islands, spread across a vast sea , appear before them. He goes on the say :

The Lady needs to rule the masses and take important decisions. Let us see how well can you do that. These are N Islands, indexed from 1 to N. There are M bidirectional roads in total, wherein each road connects 2 distinct Islands and multiple roads may connect a pair of Islands. Each of the first K Islands i.e. Islands with index from 1 to K, have a soldier who fought valiantly in the battle and wants to get to a shelter. Each of the last K Islands i.e. Island with index from N - K + 1 to N, have a shelter home that can house only 1 Soldier.

These soldiers await your commands. The cost effort of reaching a shelter for a soldier is the distance that has to be traveled. In addition, you have the option of using magic to transport the soldiers. One use of magic will allow you to move any solider from any island to any other island. Using your magic once costs 10^4 units of effort. You can always use your magic, but then again it comes at a huge cost. Give a target shelter to each of the soldiers and minimize the overall cost efforts of the scenario.

Help Gudi find the minimum cost efforts.

HackerEarth Encounter with the Lord problem solution.

#include<bits/stdc++.h>
 
 
using namespace std;
 
#define gc getchar_unlocked
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define elif else if
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define N 205 //max number of vertices in one part
#define INF 100000000 //just infinity

int cost[N][N]; //cost matrix
int n, max_match; //n workers and n jobs
int lx[N], ly[N]; //labels of X and Y parts
int xy[N]; //xy[x] - vertex that is matched with x,
int yx[N]; //yx[y] - vertex that is matched with y
bool S[N], T[N]; //sets S and T in algorithm
int slack[N]; //as in the algorithm description
int slackx[N]; //slackx[y] such a vertex, that
// l(slackx[y]) + l(y) - w(slackx[y],y) = slack[y]
int prv[N]; //array for memorizing alternating paths
void init_labels()
{
  memset(lx, 0, sizeof(lx));
  memset(ly, 0, sizeof(ly));
  for (int x = 0; x < n; x++)
    for (int y = 0; y < n; y++)
      lx[x] = max(lx[x], cost[x][y]);
}
void update_labels()
{
  int x, y, delta = INF; //init delta as infinity
  for (y = 0; y < n; y++) //calculate delta using slack
    if (!T[y])
    delta = min(delta, slack[y]);
  for (x = 0; x < n; x++) //update X labels
    if (S[x]) lx[x] -= delta;
  for (y = 0; y < n; y++) //update Y labels
    if (T[y]) ly[y] += delta;
  for (y = 0; y < n; y++) //update slack array
    if (!T[y])
    slack[y] -= delta;
}
void add_to_tree(int x, int prevx)
//x - current vertex,prevx - vertex from X before x in the alternating path,
//so we add edges (prevx, xy[x]), (xy[x], x)
{
  S[x] = true; //add x to S
  prv[x] = prevx; //we need this when augmenting
  for (int y = 0; y < n; y++) //update slacks, because we add new vertex to S
    if (lx[x] + ly[y] - cost[x][y] < slack[y])
    {
      slack[y] = lx[x] + ly[y] - cost[x][y];
      slackx[y] = x;
    }
}
void augment() //main function of the algorithm
{
  if (max_match == n) return; //check wether matching is already perfect
  int x, y, root; //just counters and root vertex
  int q[N], wr = 0, rd = 0; //q - queue for bfs, wr,rd - write and read
  //pos in queue
  memset(S, false, sizeof(S)); //init set S
  memset(T, false, sizeof(T)); //init set T
  memset(prv, -1, sizeof(prv)); //init set prev - for the alternating tree
  for (x = 0; x < n; x++) //finding root of the tree
    if (xy[x] == -1)
    {
      q[wr++] = root = x;
      prv[x] = -2;
      S[x] = true;
      break;
    }
  for (y = 0; y < n; y++) //initializing slack array
  {
    slack[y] = lx[root] + ly[y] - cost[root][y];
    slackx[y] = root;
  }
  //second part of augment() function
  while (true) //main cycle
  {
    while (rd < wr) //building tree with bfs cycle
    {
      x = q[rd++]; //current vertex from X part
      for (y = 0; y < n; y++) //iterate through all edges in equality graph
        if (cost[x][y] == lx[x] + ly[y] && !T[y])
        {
          if (yx[y] == -1) break; //an exposed vertex in Y found, so
          //augmenting path exists!
          T[y] = true; //else just add y to T,
          q[wr++] = yx[y]; //add vertex yx[y], which is matched
          //with y, to the queue
          add_to_tree(yx[y], x); //add edges (x,y) and (y,yx[y]) to the tree
        }
      if (y < n) break; //augmenting path found!
    }
    if (y < n) break; //augmenting path found!
    update_labels(); //augmenting path not found, so improve labeling
    wr = rd = 0;
    for (y = 0; y < n; y++)
    //in this cycle we add edges that were added to the equality graph as a
    //result of improving the labeling, we add edge (slackx[y], y) to the tree if
    //and only if !T[y] && slack[y] == 0, also with this edge we add another one
    //(y, yx[y]) or augment the matching, if y was exposed
      if (!T[y] && slack[y] == 0)
      {
        if (yx[y] == -1) //exposed vertex in Y found - augmenting path exists!
        {
          x = slackx[y];
          break;
        }
        else
        {
          T[y] = true; //else just add y to T,
          if (!S[yx[y]])
          {
            q[wr++] = yx[y]; //add vertex yx[y], which is matched with
            //y, to the queue
            add_to_tree(yx[y], slackx[y]); //and add edges (x,y) and (y,
            //yx[y]) to the tree
          }
        }
      }
      if (y < n) break; //augmenting path found!
  }
    if (y < n) //we found augmenting path!
    {
      max_match++; //increment matching
      //in this cycle we inverse edges along augmenting path
      for (int cx = x, cy = y, ty; cx != -2; cx = prv[cx], cy = ty)
      {
        ty = xy[cx];
        yx[cy] = cx;
        xy[cx] = cy;
      }
      augment(); //recall function, go to step 1 of the algorithm
    }
}//end of augment() function
int hungarian()
{
  int ret = 0; //weight of the optimal matching
  max_match = 0; //number of vertices in current matching
  memset(xy, -1, sizeof(xy));
  memset(yx, -1, sizeof(yx));
  init_labels(); //step 0
  augment(); //steps 1-3
  for (int x = 0; x < n; x++) //forming answer there
     ret += cost[x][xy[x]];
  return ret;
}

int gcd(int u, int v) {
return (v != 0)?gcd(v, u%v):u;
}
int inp[205]={0};
int dist[205][205];
int gr[205][205];
int main () 
{
  // freopen("in.txt","r",stdin);
  // freopen("out","w",stdout);
  int t,m,i,j,k,no;
  cin >> t;
  while (t--)
  {
    cin>>no>>m>>n;
   for(i=0;i<n;i++)
      for(j=0;j<n;j++)
          cost[i][j]=0;
    for(i=0;i<no;i++)
    {
      for(j=0;j<no;j++)
        dist[i][j]=gr[i][j]=INF;
    }
    while(m--)
    {
       int ta,tb,tc;
       cin>>ta>>tb>>tc;
       ta--;
       tb--;
       int prev = gr[ta][tb];
       tc=min(tc,prev); 
       gr[ta][tb]=gr[tb][ta]=tc;
       dist[ta][tb]=dist[tb][ta]=tc;
    }
     // <Floyd>     
    for (i=0;i<no;i++)
    {
      for(j=0;j<no;j++)
      {
        for(k=0;k<no;k++)
        {
           dist[j][k] = min( dist[j][k], dist[j][i]+dist[i][k]);
        }
      }
    }
    // </Floyd>

    for(i=0;i<n;i++)
    {
      for(j=0;j<n;j++)
      {
        cost[i][j] = min(10000,dist[i][no-n+j]) ;
        cost[i][j]= -1*cost[i][j];
      }
    }
    ll int  ans = hungarian();
    cout << -1*ans;
    if(t>0)
      cout<<endl;
  }
return 0;
}

Second solution

import java.io.*;
import java.util.*;

public class fprb {
  private static InputReader in;
  private static PrintWriter out;

  public static void main(String[] args) throws IOException {
    in = new InputReader(System.in);
    out = new PrintWriter(System.out, true);

    int t = in.nextInt();
    while(t-->0) {
      int n = in.nextInt(), m = in.nextInt(), k = in.nextInt();
      N = k+k+2;
      cap = new int[N][N];
      cost = new int[N][N];
      pot = new int[N];
      int[][] d = new int[n][n];
      for (int i = 0; i < n; i++) {
        Arrays.fill(d[i], 10000);
        d[i][i] = 0;
      }
      for (int i = 0; i < m; i++) {
        int a = in.nextInt()-1, b = in.nextInt()-1, c = in.nextInt();
        d[a][b] = Math.min(d[a][b],c);
        d[b][a] = Math.min(d[b][a],c);
      }
      for (int r = 0; r < n; r++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) d[i][j] = Math.min(d[i][j],d[i][r]+d[r][j]);
      for (int i = 0; i < k; i++) {
        for (int j = n-k; j < n; j++) {
          addEdge(i,j-n+k+k,1,d[i][j]);
        }
        addEdge(N-1,i,1,0);
        addEdge(i+k,N-2,1,0);
      }
      out.println(flow(N-1,N-2)[1]);
    }
    
    out.close();
    System.exit(0);
  }
  public static int N;
  public static int INF = 1 << 29;
  private static int[][] cap, cost;
  private static int[] pot;

  // add an edge from x to y with capacity w and cost c
  private static void addEdge(int x, int y, int w, int c) {
    cap[x][y] = w;
    cost[x][y] = c;
    cost[y][x] = -c;
  }

  // if we want max cost, take replace c with Q - c, (Q > all c)
  // then take Q * flow [0] - flow [1]
  private static int[] flow(int source, int sink) {
    int ans_flow = 0, ans_cost = 0;
    pot = new int[N]; // potential of the node

    while (true) {
      boolean[] used = new boolean[N];
      int[] dist = new int[N], prev = new int[N];
      Arrays.fill(dist, INF);
      dist[source] = 0;

      while (true) {
        int x = -1;
        for (int i = 0; i < N; i++)
          if (dist[i] != INF && !used[i] && (x == -1 || dist[i] < dist[x]))
            x = i;

        if (x == -1)
          break;

        used[x] = true;
        for (int i = 0; i < N; i++)
          if (cap[x][i] > 0 && dist[x] + cost[x][i] + pot[x] - pot[i] < dist[i]) {
            dist[i] = dist[x] + cost[x][i] + pot[x] - pot[i];
            prev[i] = x;
          }
      }

      if (!used[sink])
        break;

      int ansf = INF, ansc = 0;
      for (int x = sink; x != source; x = prev[x])
        ansf = Math.min(ansf, cap[prev[x]][x]);

      ans_flow += ansf;
      for (int x = sink; x != source; x = prev[x]) {
        ansc += cost[prev[x]][x] * ansf;
        cap[prev[x]][x] -= ansf;
        cap[x][prev[x]] += ansf;
      }

      for (int i = 0; i < N; i++)
        pot[i] += dist[i];

      ans_flow += ansf;
      ans_cost += ansc;
    }

    return new int[] {ans_flow, ans_cost};
    // returns both flow and cost
  }

  static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream), 32768);
      tokenizer = null;
    }

    public String next() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }
  }

}