Обсуждение:Венгерский алгоритм

this algorithm doesn't work! my implementation doesn't pass some tests, for example: 4 774 473 548 70 341 197 218 275 987 165 650 109 546 358 629 950 you'd better change algorithm or erase it nobody to be disappointed like I am now.(((

P.S. this is my implementation(you can be sure there is no errors)

1. include<iostream>
2. include<vector>
3. include<stack>
4. include<ctime>

using namespace std; int n; vector<bool> used; vector<int> p; vector<vector<int> > v; const int INF = 1000000000;

void null_rows(vector<vector<int> > &v) { for(int i = 0; i < n; i++) { int mini = INF; for(int j = 0; j < n; j++) mini = min(mini, v[i][j]); for(int j = 0; j < n; j++) v[i][j] -= mini; }

return; }

void null_cols(vector<vector<int> > &v) { for(int i = 0; i < v.size(); i++) { int mini = INF; for(int j = 0; j < n; j++) mini = min(mini, v[j][i]); for(int j = 0; j < n; j++) v[j][i] -= mini; }

return; }

bool kuhn(int a) { if(used[a]) return false; used[a] = true; for(int i = 0; i < n; i++) if(v[a][i] == 0 && (p[i] == -1 || kuhn(p[i]))) { p[i] = a; return true; } return false; }

void make_null() { used = vector<bool> (2*n);

vector<bool> u(n);

stack<int> s; for(int i = 0; i < n; i++) if(p[i] != -1) u[p[i]] = true;

for(int i = 0; i < n; i++) if(!u[i]) { used[i] = true; s.push(i); }

while(!s.empty()) { int top = s.top(); s.pop(); if(top >= n) { for(int i = 0; i < n; i++) if(v[i][top-n] == 0 && !used[i]) { used[i] = true; s.push(i); } } else { for(int i = 0; i < n; i++) if(v[top][i] == 0 && !used[i+n]) { used[i+n] = true; s.push(i+n); } } }

int mini = INF; for(int i = 0; i < n; i++) if(used[i]) for(int j = 0; j < n; j++) if(!used[j+n]) mini = min(mini, v[i][j]);

for(int i = 0; i < n; i++) if(used[i]) for(int j = 0; j < n; j++) v[i][j] -= mini; for(int i = 0; i < n; i++) if(used[i+n]) for(int j = 0; j < n; j++) v[j][i] += mini;

return; }

bool fill_p() { p = vector<int> (n, -1); used = vector<bool> (n); for(int i = 0; i < n; i++) { fill(used.begin(), used.end(), false); kuhn(i); } int cnt = 0; for(int i = 0; i < n; i++) if(p[i] != -1) cnt++;

return cnt == n; }

int main() { srand(time(NULL)); cin >> n;

v = vector<vector<int> > (n, vector<int> (n));

for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) cin >> v[i][j];

while(true) { null_rows(v); if(fill_p()) break;

null_cols(v); if(fill_p()) break;

make_null(); }

for(int i = 0; i < n; i++) cout << p[i] << "-th worker does " << i << "-th work" << endl;

return 0; }

91.214.128.22 14:09, 7 августа 2010 (UTC)Ismailov Ibragim