01/10/2018, 10:05

Mọi người xem giùm mình bài c++ này sai ở đâu vậy

#include <iostream>
 #include <stdio.h>
#include <string.h>
 #define N 55 //max number of vertices in one part
 #define INF 100000000 //just infinity
using namespace std;
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 prev[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 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(prev, -1, sizeof(prev)); //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;
 prev[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;
 }
 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
 prev[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;
 }
}
//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!
 //(y, yx[y]) or augment the matching, if y was exposed
 if (!T[y] && slack[y] == 0)

 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
 {
 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 = prev[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;
}
Henry viết 12:21 ngày 01/10/2018

Này có phải copy code ở trên mạng không thế mà comment dữ vậy?

HK boy viết 12:05 ngày 01/10/2018

Format code bạn ơi. Thêm 3 dấu ` vào đầu và cuối code.
Mà code này trông lạ quá, tại sao có hungarian ở đây nhỉ??

Tan Pham viết 12:14 ngày 01/10/2018

là sao bạn
nghĩa là mình thêm như bên dưới hả bạn. Sao thấy ``` lạ quá

``` #include
....
return ret; ```
HK boy viết 12:18 ngày 01/10/2018

Nó chính là nút bên cạnh số 1 trên bàn phím chính của bạn…

Tan Pham viết 12:08 ngày 01/10/2018

sao thêm vào nó báo lỗi ta

rogp10 viết 12:09 ngày 01/10/2018

Cái dấu đó (không cần 3 dấu đâu bạn, 1 thôi) là mã trên diễn đàn.

HK boy viết 12:15 ngày 01/10/2018

Khi bạn up code lên diễn đàn mới cần thêm 3 dấu `, còn bình thường bạn code trên IDE thì cần gì thêm.

Tan Pham viết 12:15 ngày 01/10/2018

mình chạy cái đó mà sao nó cứ hiện ra lỗi nãy

HK boy viết 12:19 ngày 01/10/2018

Mình không biết là code này căn dòng tệ hại hay bạn sửa lại nữa.
Lỗi khi thừa thiếu { gì đấy. Bạn căn dòng lại đi, căng dòng thế này thì Chúa cũng chả ngó được code.

@graktung: Code copy trên mạng mà căn dòng xấu thế này thì…

Henry viết 12:18 ngày 01/10/2018

Code copy trên mạng mà căn dòng xấu thế này thì…

Lỡ copy về thấy chưa thẳng hàng thế là căn lề trái thì làm sao :|?

HK boy viết 12:06 ngày 01/10/2018

Thảm hoạ nhất là thấy code người ta indent tử tế, không hợp ý mình liền copy về và bỏ hết indent…
Hình như thớt này rơi vào tình trạng “thảm hoạ”…

Henry viết 12:20 ngày 01/10/2018

Em chỉ mới phỏng đoán đã nói là 100% đâu.

HK boy viết 12:10 ngày 01/10/2018

ncl Nói chung là code xấu mà cmt tử tế thì chỉ có thể là…
hoy kệ đi

p/s: Nghe lời @graktung

Henry viết 12:06 ngày 01/10/2018

ncl

Mới nhìn hiểu lầm. Tránh viết tắt mấy chữ như thế

Bài liên quan
0