fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. const int maxN = 105;
  5.  
  6. class Solution {
  7.   public:
  8.  
  9.     int cost[maxN][maxN]; //cost matrix
  10.     int n, max_match; //n workers and n jobs
  11.     int lx[maxN], ly[maxN]; //labels of X and Y parts
  12.     int xy[maxN]; //xy[x] - vertex that is matched with x,
  13.     int yx[maxN]; //yx[y] - vertex that is matched with y
  14.     bool S[maxN], T[maxN]; //sets S and T in algorithm
  15.     int slack[maxN]; //as in the algorithm description
  16.     int slackx[maxN]; //slackx[y] such a vertex, that
  17.     int prev_ious[maxN]; //array for memorizing alternating p
  18.  
  19.     void init_labels()
  20.     {
  21.         memset(lx, 0, sizeof(lx));
  22.         memset(ly, 0, sizeof(ly));
  23.         for (int x = 0; x < n; x++)
  24.         for (int y = 0; y < n; y++)
  25.         lx[x] = max(lx[x], cost[x][y]);
  26.     }
  27.  
  28.  
  29.     void update_labels()
  30.     {
  31.         int x, y;
  32.         int delta = 1e16; //init delta as infinity
  33.         for (y = 0; y < n; y++) //calculate delta using slack
  34.             if (!T[y])
  35.                 delta = min(delta, slack[y]);
  36.         for (x = 0; x < n; x++) //update X labels
  37.             if (S[x])
  38.                 lx[x] -= delta;
  39.         for (y = 0; y < n; y++) //update Y labels
  40.             if (T[y])
  41.                 ly[y] += delta;
  42.         for (y = 0; y < n; y++) //update slack array
  43.             if (!T[y])
  44.                 slack[y] -= delta;
  45.     }
  46.  
  47.  
  48.     void add_to_tree(int x, int prev_iousx) 
  49.     //x - current vertex,prev_iousx - vertex from X before x in the alternating path,
  50.     //so we add edges (prev_iousx, xy[x]), (xy[x], x)
  51.     {
  52.         S[x] = true; //add x to S
  53.         prev_ious[x] = prev_iousx; //we need this when augmenting
  54.         for (int y = 0; y < n; y++) //update slacks, because we add new vertex to S
  55.             if (lx[x] + ly[y] - cost[x][y] < slack[y])
  56.             {
  57.                 slack[y] = lx[x] + ly[y] - cost[x][y];
  58.                 slackx[y] = x;
  59.             }
  60.     }
  61.  
  62.  
  63.  
  64.     void augment() //main function of the algorithm
  65.     {
  66.         if (max_match == n) return; //check whether matching is already perfect
  67.         int x, y, root; //just counters and root vertex
  68.         int q[maxN], wr = 0, rd = 0; //q - queue for bfs, wr,rd - write and read
  69.         //pos in queue
  70.         memset(S, false, sizeof(S)); //init set S
  71.         memset(T, false, sizeof(T)); //init set T
  72.         memset(prev_ious, -1, sizeof(prev_ious)); //init set prev_ious - for the alternating tree
  73.  
  74.         for (x = 0; x < n; x++) //finding root of the tree
  75.         {
  76.             if (xy[x] == -1)
  77.             {
  78.                 q[wr++] = root = x;
  79.                 prev_ious[x] = -2;
  80.                 S[x] = true;
  81.                 break;
  82.             }
  83.         }
  84.  
  85.         for (y = 0; y < n; y++) //initializing slack array
  86.         {
  87.             slack[y] = lx[root] + ly[y] - cost[root][y];
  88.             slackx[y] = root;
  89.         }
  90.  
  91.         //second part of augment() function
  92.         while (true) //main cycle
  93.         {
  94.             while (rd < wr) //building tree with bfs cycle
  95.             {
  96.                 x = q[rd++]; //current vertex from X part
  97.                 for (y = 0; y < n; y++) //iterate through all edges in equality graph
  98.                     if (cost[x][y] == lx[x] + ly[y] && !T[y])
  99.                     {
  100.                         if (yx[y] == -1) break; //an exposed vertex in Y found, so
  101.                                                 //augmenting path exists!
  102.                             T[y] = true; //else just add y to T,
  103.                         q[wr++] = yx[y]; //add vertex yx[y], which is matched
  104.                         //with y, to the queue
  105.                         add_to_tree(yx[y], x); //add edges (x,y) and (y,yx[y]) to the tree
  106.                     }
  107.                 if (y < n)
  108.                     break; //augmenting path found!
  109.             }
  110.             if (y < n)
  111.                 break; //augmenting path found!
  112.  
  113.             update_labels(); //augmenting path not found, so improve labeling
  114.  
  115.             wr = rd = 0; 
  116.             for (y = 0; y < n; y++) 
  117.             //in this cycle we add edges that were added to the equality graph as a
  118.             //result of improving the labeling, we add edge (slackx[y], y) to the tree if
  119.             //and only if !T[y] && slack[y] == 0, also with this edge we add another one
  120.             //(y, yx[y]) or augment the matching, if y was exposed
  121.             if (!T[y] && slack[y] == 0)
  122.             {
  123.                 if (yx[y] == -1) //exposed vertex in Y found - augmenting path exists!
  124.                 {
  125.                     x = slackx[y];
  126.                     break;
  127.                 }
  128.                 else
  129.                 {
  130.                     T[y] = true; //else just add y to T,
  131.                     if (!S[yx[y]]) 
  132.                     {
  133.                         q[wr++] = yx[y]; //add vertex yx[y], which is matched with
  134.                         //y, to the queue
  135.                         add_to_tree(yx[y], slackx[y]); //and add edges (x,y) and (y,
  136.                         //yx[y]) to the tree
  137.                     }
  138.                 }
  139.             }
  140.             if (y < n) break; //augmenting path found!
  141.         }
  142.  
  143.         if (y < n) //we found augmenting path!
  144.         {
  145.             max_match++; //increment matching
  146.             //in this cycle we inverse edges along augmenting path
  147.             for (int cx = x, cy = y, ty; cx != -2; cx = prev_ious[cx], cy = ty)
  148.             {
  149.                 ty = xy[cx];
  150.                 yx[cy] = cx;
  151.                 xy[cx] = cy;
  152.             }
  153.             augment(); //recall function, go to step 1 of the algorithm
  154.         }
  155.     }//end of augment() function
  156.  
  157.     int hungarian()
  158.     {
  159.         int ret = 0; //weight of the optimal matching
  160.         max_match = 0; //number of vertices in current matching
  161.         memset(xy, -1, sizeof(xy)); 
  162.         memset(yx, -1, sizeof(yx));
  163.         init_labels(); //step 0
  164.         augment(); //steps 1-3
  165.  
  166.         for (int x = 0; x < n; x++) //forming answer there
  167.             ret += cost[x][xy[x]];
  168.  
  169.         return ret;
  170.     }
  171.  
  172.     int assignmentProblem(int Arr[], int N) {
  173.  
  174.         n = N;
  175.         for(int i=0; i<n; i++)
  176.             for(int j=0; j<n; j++)
  177.                 cost[i][j] = -1*Arr[i*n+j];
  178.  
  179.         int ans = -1 * hungarian();
  180.  
  181.         return ans;
  182.     }
  183. };
  184.  
  185. signed main()
  186. {
  187.   ios_base::sync_with_stdio(false);
  188.   cin.tie(0);cout.tie(0);
  189.  
  190.   int t;
  191.   cin >> t;
  192.   while (t--){
  193.   	 int n;
  194.   	 cin >> n;
  195.   	 int a[n*n];
  196.   	 for (int i = 0 ; i < n ; i++)
  197.   	   for (int j = 0 ; j < n ; j++) cin >> a[i*n + j];
  198.  
  199. 	   Solution ob;
  200.        cout<< ob.assignmentProblem(a,n)<< "\n";
  201.   }
  202.  
  203.   return 0;
  204. }
Success #stdin #stdout 0s 5268KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/J6MOSp
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!