Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 13.05.2010, 19:27   #1
Joe89
 
Регистрация: 13.05.2010
Сообщений: 4
По умолчанию Венгерский алгоритм(с++)

Нужно реализовать венгерский метод решения задачи о назначении.
Имеется даный код:
Код:
#include <vector>
using std::vector;



const int INF = 1000*1000*1000;

int n;
vector < vector<int> > a;
vector<int> xy, yx;
vector<char> vx, vy;
vector<int> minrow, mincol;

bool dotry (int i) {
     if (vx[i])  return false;
     vx[i] = true;
     for (int j=0; j<n; ++j)
          if (a[i][j]-minrow[i]-mincol[j] == 0)
               vy[j] = true;
     for (int j=0; j<n; ++j)
          if (a[i][j]-minrow[i]-mincol[j] == 0 && yx[j] == -1) {
               xy[i] = j;
               yx[j] = i;
               return true;
          }
     for (int j=0; j<n; ++j)
          if (a[i][j]-minrow[i]-mincol[j] == 0 && dotry (yx[j])) {
               xy[i] = j;
               yx[j] = i;
               return true;
          }
     return false;
}

int main() {

     
     
     mincol.assign (n, INF);
     minrow.assign (n, INF);
     for (int i=0; i<n; ++i)
          for (int j=0; j<n; ++j)
               minrow[i] = min (minrow[i], a[i][j]);
     for (int j=0; j<n; ++j)
          for (int i=0; i<n; ++i)
               mincol[j] = min (mincol[j], a[i][j] - minrow[i]);

     xy.assign (n, -1);
     yx.assign (n, -1);
     for (int c=0; c<n; ) {
          vx.assign (n, 0);
          vy.assign (n, 0);
          int k = 0;
          for (int i=0; i<n; ++i)
               if (xy[i] == -1 && dotry (i))
                    ++k;
          c += k;
          if (k == 0) {
               int z = INF;
               for (int i=0; i<n; ++i)
                    if (vx[i])
                         for (int j=0; j<n; ++j)
                              if (!vy[j])
                                   z = min (z, a[i][j]-minrow[i]-mincol[j]);
               for (int i=0; i<n; ++i) {
                    if (vx[i]) minrow[i] += z;
                    if (vy[i]) mincol[i] -= z;
               }
          }
     }

     int ans = 0;
     for (int i=0; i<n; ++i)
          ans += a[i][xy[i]];
     printf ("%d\n", ans);
     for (int i=0; i<n; ++i)
          printf ("%d ", xy[i]+1);

}
По-идее все должно работать, но компилятор ругается:

C:\Program Files\Microsoft Visual Studio\VC98\C1.cpp(20) : error C2374: 'j' : redefinition; multiple initialization
C:\Program Files\Microsoft Visual Studio\VC98\C1.cpp(17) : see declaration of 'j'
C:\Program Files\Microsoft Visual Studio\VC98\C1.cpp(26) : error C2374: 'j' : redefinition; multiple initialization
C:\Program Files\Microsoft Visual Studio\VC98\C1.cpp(17) : see declaration of 'j'
C:\Program Files\Microsoft Visual Studio\VC98\C1.cpp(43) : error C2065: 'min' : undeclared identifier
C:\Program Files\Microsoft Visual Studio\VC98\C1.cpp(65) : error C2374: 'i' : redefinition; multiple initialization
C:\Program Files\Microsoft Visual Studio\VC98\C1.cpp(60) : see declaration of 'i'
C:\Program Files\Microsoft Visual Studio\VC98\C1.cpp(73) : error C2374: 'i' : redefinition; multiple initialization
C:\Program Files\Microsoft Visual Studio\VC98\C1.cpp(41) : see declaration of 'i'
C:\Program Files\Microsoft Visual Studio\VC98\C1.cpp(76) : error C2374: 'i' : redefinition; multiple initialization
C:\Program Files\Microsoft Visual Studio\VC98\C1.cpp(41) : see declaration of 'i'
C:\Program Files\Microsoft Visual Studio\VC98\C1.cpp(79) : warning C4508: 'main' : function should return a value; 'void' return type assumed
Error executing cl.exe.

Подскажите в чем проблема и как ее решить.
Буду очень благодарен за помощь.
Joe89 вне форума Ответить с цитированием
Старый 13.05.2010, 22:57   #2
Z1000000
Форумчанин
 
Регистрация: 04.05.2010
Сообщений: 495
По умолчанию

Внутри одной процедуры не надо по нескольку раз объявлять тип
Код:
for (int i=0; i<n; ++i) {
Один раз объявил , дальше в этой процедуре, просто без int
Код:
for (i=0; i<n; ++i) {
и функция min ему незнакома может библиотеку какую не подключил.

Код:
#include<algorithm>
вроде эту
Нажми на весы, поставь +
Для благодарностей : WebMoney WMR R252732729948
Z1000000 вне форума Ответить с цитированием
Старый 13.05.2010, 23:03   #3
Joe89
 
Регистрация: 13.05.2010
Сообщений: 4
По умолчанию

О, спасибо.
только остались эти ошибки:
C:\Program Files\Microsoft Visual Studio\VC98\C1.cpp(44) : error C2065: 'min' : undeclared identifier
C:\Program Files\Microsoft Visual Studio\VC98\C1.cpp(80) : warning C4508: 'main' : function should return a value;
Joe89 вне форума Ответить с цитированием
Старый 14.05.2010, 00:31   #4
Joe89
 
Регистрация: 13.05.2010
Сообщений: 4
По умолчанию

Цитата:
Сообщение от Z1000000 Посмотреть сообщение
и функция min ему незнакома может библиотеку какую не подключил.

Код:
#include<algorithm>
вроде эту
подключил. но все равно пишет ошибку
Joe89 вне форума Ответить с цитированием
Старый 14.05.2010, 20:00   #5
Joe89
 
Регистрация: 13.05.2010
Сообщений: 4
По умолчанию

Спасибо!
Библиотеку подключил, но ошибка осталась:
C:\Program Files\Microsoft Visual Studio\VC98\C1.cpp(43) : error C2065: 'min' : undeclared identifier
Joe89 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

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

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Волновой алгоритм (алгоритм Ли) MrRockchip Общие вопросы C/C++ 4 10.05.2010 13:26
Алгоритм. Paradigma Помощь студентам 7 31.03.2010 16:01
Задачи о назначениях. Венгерский алгоритм. PSix1_73 Паскаль, Turbo Pascal, PascalABC.NET 0 04.06.2009 00:41
Алгоритм?! Spartaner Фриланс 2 28.05.2009 03:22