Меню
Главная
Случайная статья
Настройки
|
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)
- include<iostream>
- include<vector>
- include<stack>
- include<ctime>
using namespace std;
int n;
vector used;
vector p;
vector > v;
const int INF = 1000000000;
void null_rows(vector > &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 > &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 (2*n);
vector u(n);
stack 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 (n, -1);
used = vector (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 > (n, vector (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[ответить]
|
|