Welcome to ShenZhenJia Knowledge Sharing Community for programmer and developer-Open, Learning and Share
menu search
person
Welcome To Ask or Share your Answers For Others

Categories

This is my code and i want to delete last line of it's output: This is about data-structure and here is the code i took and changed some lines but i can't undrestand what can i do for solve the problem.

#include <bits/stdc++.h>
using namespace std;
#define N 4

struct Node
{
    Node* parent;
    int pathCost;
    int cost;
    int workerID;
    int jobID;
    bool assigned[N];
};
Node* newNode(int x, int y, bool assigned[],
              Node* parent)
{
    Node* node = new Node;
    for (int j = 0; j < N; j++)
        node->assigned[j] = assigned[j];
    node->assigned[y] = true;
    node->parent = parent;
    node->workerID = x;
    node->jobID = y;
    return node;
}
int calculateCost(int costMatrix[N][N], int x,
                  int y, bool assigned[])
{
    int cost = 0;
    bool available[N] = {true};
    for (int i = x + 1; i < N; i++)
    {
        int min = INT_MAX, minIndex = -1;
        for (int j = 0; j < N; j++)
        {
            if (!assigned[j] && available[j] &&
                costMatrix[i][j] < min)
            {
                minIndex = j;
                min = costMatrix[i][j];
            }
        }
        cost += min;
        available[minIndex] = false;
    }
    return cost;
}
struct comp
{
    bool operator()(const Node* lhs,
                   const Node* rhs) const
    {
        return lhs->cost > rhs->cost;
    }
};
void printAssignments(Node *min)
{
    if(min->parent==NULL)
        return;
    printAssignments(min->parent);
    cout << min->jobID << endl;
}
int findMinCost(int costMatrix[N][N])
{
    priority_queue<Node*, std::vector<Node*>, comp> pq;
    bool assigned[N] = {false};
    Node* root = newNode(-1, -1, assigned, NULL);
    root->pathCost = root->cost = 0;
    root->workerID = -1;
    pq.push(root);
    while (!pq.empty())
    {
      Node* min = pq.top();
      pq.pop();
      int i = min->workerID + 1;
      if (i == N)
      {
          printAssignments(min);
          return min->cost;
      }
      for (int j = 0; j < N; j++)
      {
        if (!min->assigned[j])
        {
          Node* child = newNode(i, j, min->assigned, min);
          child->pathCost = min->pathCost + costMatrix[i][j];
          child->cost = child->pathCost +
            calculateCost(costMatrix, i, j, child->assigned);
          pq.push(child);
        }
      }
    }
}
int main()
{
    int n;
    cin >> n;
    int inputarray[N][N];
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++) {
            cin >> inputarray[i][j];
        }
    }
    cout << findMinCost(inputarray);
    return 0;
}

This is My input:

4
9 2 7 8
6 4 3 7
5 8 1 8
7 6 9 4

And ouput:

1
0
2
3
13

But i just want the first 4 line of output. what should i do? any help?

Let there be N workers and N jobs. Any worker can be assigned to perform any job, incurring some cost that may vary depending on the work-job assignment. It is required to perform all jobs by assigning exactly one worker to each job and exactly one job to each agent in such a way that the total cost of the assignment is minimized.

jobassignment


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
thumb_up_alt 0 like thumb_down_alt 0 dislike
263 views
Welcome To Ask or Share your Answers For Others

1 Answer

等待大神答复

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
thumb_up_alt 0 like thumb_down_alt 0 dislike
Welcome to ShenZhenJia Knowledge Sharing Community for programmer and developer-Open, Learning and Share
...