Тема: Vengerskiy Algoritm za O(n^3)
Plz , скинте реализацию Венгерского алгоритма за O(n^3).
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Algo » Vengerskiy Algoritm za O(n^3)
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Plz , скинте реализацию Венгерского алгоритма за O(n^3).
Когда то писал эту задачу, код сохранился. По моему, он решает не на минимум, а на максимум, но за O(N^3)
#include <cstdio>
#include <cstring>
const int MAX=701;
int a[MAX][MAX];
int n;
int x[MAX], y[MAX], sx[MAX], sy[MAX], mx[MAX], my[MAX];
inline int get(int x,int y)
{
return a[x][y]-mx[x]-my[y];
}
bool go(int cur)
{
sx[cur]=1;
for(int i=0;i<n;i++)
{
if(get(cur,i)==0)
{
if(y[i]==-1)
{
sy[i]=cur;
while(1)
{
int t=x[cur];
x[cur]=i;
y[i]=cur;
if(~t)
{
cur=sy[t];
i=t;
}
else break;
}
return true;
}
}
}
for(int i=0;i<n;i++)
{
if(get(cur,i)==0)
{
if(!sx[y[i]])
{
sy[i]=cur;
if(go(y[i]))
{
return true;
}
}
}
}
return false;
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
mx[i]=-50000;
for(int j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]>mx[i])mx[i]=a[i][j];
}
}
for(int i=0;i<n;i++)
{
int m=-50000;
for(int j=0;j<n;j++)
{
int t=get(j,i);
if(t>m)m=t;
}
my[i]=m;
}
memset(x,-1,sizeof x);
memset(y,-1,sizeof y);
for(int sc=0;sc<n;sc++)
{
memset(sx,0,sizeof sx);
memset(sy,-1,sizeof sy);
bool b=go(sc);
while(!b)
{
int m=-50000, dx;
for(int i=0;i<n;i++)
{
if(sx[i])
{
for(int j=0;j<n;j++)
{
if(!(~sy[j]))
{
int t=get(i,j);
if(m<t)
{
m=t;
dx=i;
}
}
}
}
}
for(int i=0;i<n;i++)
{
if(sx[i])mx[i]+=m;
if(~sy[i])my[i]-=m;
}
b=go(dx);
}
}
for(int i=0;i<n;i++)
{
printf("%d ",x[i]+1);
}
}
а тут можно прочитать подробное объяснение этого алгоритма http://www.topcoder.com/tc?module=Stati … nAlgorithm
Когда то писал эту задачу, код сохранился. По моему, он решает не на минимум, а на максимум, но за O(N^3)
#include <cstdio> #include <cstring> const int MAX=701; int a[MAX][MAX]; int n; int x[MAX], y[MAX], sx[MAX], sy[MAX], mx[MAX], my[MAX]; inline int get(int x,int y) { return a[x][y]-mx[x]-my[y]; } bool go(int cur) { sx[cur]=1; for(int i=0;i<n;i++) { if(get(cur,i)==0) { if(y[i]==-1) { sy[i]=cur; while(1) { int t=x[cur]; x[cur]=i; y[i]=cur; if(~t) { cur=sy[t]; i=t; } else break; } return true; } } } for(int i=0;i<n;i++) { if(get(cur,i)==0) { if(!sx[y[i]]) { sy[i]=cur; if(go(y[i])) { return true; } } } } return false; } int main() { scanf("%d",&n); for(int i=0;i<n;i++) { mx[i]=-50000; for(int j=0;j<n;j++) { scanf("%d",&a[i][j]); if(a[i][j]>mx[i])mx[i]=a[i][j]; } } for(int i=0;i<n;i++) { int m=-50000; for(int j=0;j<n;j++) { int t=get(j,i); if(t>m)m=t; } my[i]=m; } memset(x,-1,sizeof x); memset(y,-1,sizeof y); for(int sc=0;sc<n;sc++) { memset(sx,0,sizeof sx); memset(sy,-1,sizeof sy); bool b=go(sc); while(!b) { int m=-50000, dx; for(int i=0;i<n;i++) { if(sx[i]) { for(int j=0;j<n;j++) { if(!(~sy[j])) { int t=get(i,j); if(m<t) { m=t; dx=i; } } } } } for(int i=0;i<n;i++) { if(sx[i])mx[i]+=m; if(~sy[i])my[i]-=m; } b=go(dx); } } for(int i=0;i<n;i++) { printf("%d ",x[i]+1); } }
А какая разница, минимум или максимум? Можно все элементы домножить на -1 и тогда минимум превратится в максимум(и наоборот).
Я знаю, просто предупредил на всякий случай
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Algo » Vengerskiy Algoritm za O(n^3)