Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 04.01.2007, 13:58
Новичок

Отправить личное сообщение для Pamc Посмотреть профиль Найти все сообщения от Pamc
 
Регистрация: 04.01.2007
Сообщений: 3

венгерский алгоритм Help!!!
Срочно нужен венгерский алгоритм реализованный на... да на чем-нибудь) Pascal, Delphi, C...
  #2  
Старый 05.01.2007, 17:12
незарегистрированный

 
Сообщений: n/a

Вот на фортране:
http://www.netlib.org/toms/548
  #3  
Старый 05.01.2007, 18:49
Новичок

Отправить личное сообщение для Pamc Посмотреть профиль Найти все сообщения от Pamc
 
Регистрация: 04.01.2007
Сообщений: 3

спасибо конечно... но нет ли на каком-нибудь другом
  #4  
Старый 05.01.2007, 19:21
Новичок

Отправить личное сообщение для it4.kp Посмотреть профиль Найти все сообщения от it4.kp
 
Регистрация: 23.09.2006
Адрес: Архангельск
Сообщений: 22

Вот на C++.
Автор: rem

Перед применением функции hungary() матрица a[][] должна
содержать соответствующие значения. После применения
минимальная перестановка будет (i,xy[i]).
Код:
#define For(i,a,b) for(int i=(int)(a);i<=(int)(b);++i)
#define Fill(a,b) memset(&a,b,sizeof(a))
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))

const int maxn=50;
const int INF=(1<<30);

int n;
int a[maxn][maxn];
int ar[maxn],ac[maxn];
int vx[maxn],vy[maxn],xy[maxn],yx[maxn];

bool dotry(int x)
{
	if (vx[x]) return false;
	vx[x]=1;
	For(y,1,n) 
		if(a[x][y]+ar[x]+ac[y]==0) vy[y]=1;
	For(y,1,n)
		if(a[x][y]+ar[x]+ac[y]==0 && yx[y]==0)
		{
			xy[x]=y;
			yx[y]=x;
			return true;
		}
	For(y,1,n)
		if(a[x][y]+ar[x]+ac[y]==0 && dotry(yx[y]))
		{
			xy[x]=y;
			yx[y]=x;
			return true;
		}
	return false;
}

void hungary()
{
	int k,z,c;
	For(i,1,n)
	{
		k=INF;
		For(j,1,n) k=Min(k,a[i][j]);
		ar[i]=-k;
	}
	For(j,1,n)
	{
		k=INF;
		For(i,1,n) k=Min(k,a[i][j]+ar[i]);
		ac[j]=-k;
	}
	Fill(xy,0);
	Fill(yx,0);
	for(c=0; c<n; )
	{
		Fill(vx,0);
		Fill(vy,0);
		k=0;
		For(i,1,n) if(xy[i]==0)
			if(dotry(i)) ++k;
		c+=k;
		if(k==0)
		{
			z=INF;
			For(i,1,n) if(vx[i]==1)
				For(j,1,n) if(vy[j]==0)
				z=Min(z,a[i][j]+ar[i]+ac[j]);
			For(i,1,n) 
			{
				if(vx[i]==1) ar[i]-=z;
				if(vy[i]==1) ac[i]+=z;
			}
		}
	}
}

Последний раз редактировалось it4.kp, 05.01.2007 в 19:25.
  #5  
Старый 05.01.2007, 20:06
Новичок

Отправить личное сообщение для Pamc Посмотреть профиль Найти все сообщения от Pamc
 
Регистрация: 04.01.2007
Сообщений: 3

спасибо!!! :d
  #6  
Старый 18.04.2008, 20:53
иыт

 
Сообщений: n/a

Єто и есть весь код венгерсого метода?
  #7  
Старый 10.06.2008, 01:13
Triny

 
Сообщений: n/a

А на Delphi есть?
  #8  
Старый 10.06.2008, 05:55
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>А на Delphi есть?
приведенный код переводится очень легко
  #9  
Старый 25.02.2010, 08:56
гость

 
Сообщений: n/a

Это не работает!
  #10  
Старый 25.02.2010, 15:26
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Это не работает!
так напиши свой!
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра