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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 09.04.2008, 22:02
гость

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

Максимальный поток в сети
Нашел в книге Окулова Программирование в алгоритмах нужный метод! Но там написано на Паскале, а я всю жизнь) писал на С++. Сколько ни пробовал перевести на С, ничо не выходит!
Следовательно либо в книге касяк, либо я транслирую плохо(скарее всего).
Не мог кто нить перевести этот алгоритм на С, либо исходник паскалевский выложить, либо свою реализацию.
З.Ы. Для построения максимального потока в сети используется метод расстанови пометок.
  #2  
Старый 27.08.2008, 13:24
гость

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

#include <stdio.h>
#include <math.h>
int C[202][202],F[202][202],P[202][2],oo=(1<<25),;
bool fl;

int MIN(int A,int B)
{
if(A<B) return A;
return B;
}

void Stream(int N,int i)
{
if(P[i][0]>0) F[P[i][0]-1][i]+=P[N-1][1];
else F[i][abs(P[i][0])-1]-=P[N-1][1];
if(abs(P[i][0])!=N-1) Stream(N,abs(P[i][0])-1);
}

void Mark(int N)
{
bool *Nnew=new bool[N];
int i,seek=N-2;
for(i=0;i<N;i++) Nnew[i]=1;
P[seek][0]=seek+1;
P[seek][1]=oo;
while(!P[N-1][0] && fl)
{
for(i=0;i<N;i++)
if(!P[i][0] && (C[seek][i] || C[i][seek]))
{
if(F[seek][i]<C[seek][i])
{
P[i][0]=seek+1;
P[i][1]=MIN(P[seek][1],C[seek][i]-F[seek][i]);
}
else if(F[i][seek]>0)
{
P[i][0]=-seek-1;
P[i][1]=MIN(P[seek][1],F[i][seek]);
}
}
Nnew[seek]=0;
seek=0;
while(seek<N && (!Nnew[seek] || !P[seek][0])) seek++;
if(seek>=N) fl=0;
}
}

//Вообще это тело мэйна
bool FordF(int N)
{
while(1)
{
for(i=0;i<N;i++) P[i][0]=0;
Mark(N);
if(!fl) break;
Stream(N,N-1);
}
}
  #3  
Старый 05.09.2008, 19:32
Новичок

Отправить личное сообщение для =[miKroZ]= Посмотреть профиль Найти все сообщения от =[miKroZ]=
 
Регистрация: 07.01.2008
Адрес: Санкт-Петербург
Сообщений: 25

вобщем, не удержался, и решил свою реализацию положить =)

Код:
#include <cstdio>
#include <memory>
#include <queue>

using namespace std;

#define task "flow"
#define MAXN 100
#define INFINITY 1000000

int c[MAXN][MAXN], f[MAXN][MAXN], cf[MAXN][MAXN];
int cut[MAXN], p[MAXN];
int n;

int bfs(int u, int v) {
  memset(cut, 0, sizeof(cut));
  memset(p, 0, sizeof(p));
  queue<int> q;
  
  q.push(u); cut[u] = 1;
  
  while (!q.empty()) {
    u = q.front(); q.pop();
    
    for (int i = 0; i < n; i++)
      if (cf[u][i] > 0 && !cut[i]) {
        q.push(i); cut[i] = 1;
        p[i] = u;
      }
  }
  
  return cut[v];
}

long long max_flow(int s, int t) {
  while (bfs(s, t)) {
    int cmin = INFINITY;
    
    int u = t;
    while (u != s) {
      if (cf[p[u]][u] < cmin)
        cmin = cf[p[u]][u];
      u = p[u];
    }
    
    u = t;
    while (u != s) {
      f[p[u]][u] += cmin;
      f[u][p[u]] -= cmin;
      cf[p[u]][u] = c[p[u]][u] - f[p[u]][u];
      cf[u][p[u]] = c[u][p[u]] - f[u][p[u]];
      
      u = p[u];
    }
  }
  
  long long flow = 0;
  
  for (int i = 0; i < n; i++)
    flow += f[i][t];
    
  return flow;
}

int main() {
  freopen(task ".in", "rt", stdin);
  freopen(task ".out", "wt", stdout);
  
  while (true) {
    scanf("%d", &n);
    
    if (0 == n)
      break;
      
    memset(c, 0, sizeof(c));
    memset(f, 0, sizeof(f));
    memset(cf, 0, sizeof(cf));
    
    int s, t, m;
    scanf("%d %d %d", &s, &t, &m);
    --s; --t;
    
    for (int i = 0; i < m; i++) {
      int u, v, w;
      scanf("%d %d %d", &u, &v, &w);
      
      c[--u][--v] += w;
      c[v][u] += w;
      cf[u][v] += w;
      cf[v][u] += w;
    }
    
    printf("%lld\n", max_flow(s, t));
  }

  return 0;
}
__________________
Irreparabilium felix oblivio rerrum.
  #4  
Старый 19.05.2010, 14:07
гость

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

только вот недодумался положить компилятор к реализации, в bc 3.1 с правкой библиотек и в builder 6 неработает
  #5  
Старый 19.05.2010, 14:30
гость

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

Сообщение от гость Посмотреть сообщение
только вот недодумался положить компилятор к реализации, в bc 3.1 с правкой библиотек и в builder 6 неработает
это дерьмо, а не компиляторы, делающие из нормальный людей интеллектуальных калек. поставь gcc (mingw, cygwin), и забудь больше про borland. она кстати банкрот, так ей и надо.
  #6  
Старый 25.05.2010, 00:43
гость

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

я учусь в универе там такие... попробуем
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
максимальный поток\ "задача о ресурсах" ExPerT Реализация, исходники, языки 0 27.03.2007 14:08
максимальны поток минимальной стоимости незарегистрированный Графы 1 28.12.2006 17:37
поток в сети jana Графы 3 11.12.2006 17:09
задача на максимальный поток (задача о ресурсах) megabot007 Задачи 4 05.12.2006 00:52
задачи на максимальный поток Olegator Задачи 5 02.11.2006 13:35