Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
ILR
11 / 0 / 0
Регистрация: 03.11.2012
Сообщений: 23
1

Алгоритм Эдмондса-Карпа, ошибка

25.01.2014, 01:36. Просмотров 1061. Ответов 1
Метки нет (Все метки)

Задача:
Янка положил на стол N выпуклых K-гранников и N различных типов наклеек по K штук каждая. Ночью кто-то наклеил наклейки на грани, по одной на грань.
Помогите Янке расставить многогранники так, чтобы наклейка каждого типа была видна pовно K-1 раз.

Решается по алгоритму Эдмондса-Карпа. На вход берёт файл, где первая строка - кол-во многогранников (и, по условию, кол-во типов наклеек), вторая - кол-во граней одного мног-ка (также кол-во наклеек одного типа), остальное - расположение наклеек, т.е. на примере, про который хочу спросить, на первом мног-ке 0 наклеек 1го типа, 3 наклейки 2го типа, 0 - 3го типа, 1 - 4го типа, 0 - 5го типа и тд.
input.txt
5
4
0 3 0 1 0
1 0 1 0 2
1 0 1 2 0
0 0 2 1 1
2 1 0 0 1

Так вот проблема в том, что при выводе этого примера получается:
C
1
2
3
4
5
6
7
addCap:error2
 
Polyhedron 1 sticker type 4
Polyhedron 2 sticker type 5
Polyhedron 3
Polyhedron 4 sticker type 3
Polyhedron 5 sticker type 2
Не могу понять, почему эта строка остаётся пустой. Где ошибка, как её исправить?
Точнее, вроде как указано, что error2, но я не достаточно разбираюсь в коде, чтобы исправить его...

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
// mnogogr.c
 
#include <stdio.h>
#include <stdlib.h>
 
int myDebug;
    //Максимальное допустимое количество многогранников
#define N_MAX 99
    //Максимальное допустимое количество узлов в сети
#define N_DIM (2*N_MAX+2)
 
    // Аварийный выход из программы
void myExit ( int i )
{
  printf("\nPress Enter");
  getc(stdin); // Нажать Enter
  exit(i); 
}
 
 
#include "queue.c"
 
typedef int network_t[N_DIM][N_DIM];
 
network_t 
  cap,   // Пропускные способности сети; от "capacity"
  flow,  // Величина потока
  rescap // Остаточная сеть; от "residual capacity"
  ;
 
int prevNodes[N_DIM]; // Номер предшествующей вершины на кратчайшем пути 
 
int N; // Количество многогранников=Количество экземпляров наклеек каждого типа
int K; // Количество граней=Количество типов наклеек
 
int sourceCode;//=0     код вершины-источника
int sinkCode;  //=2*N+1 код вершины-стока
 
 
 
 
    // Подсказка по использованию
void help ( )
{
  printf("\nUsage: <program_name> <input_file_name>  <output_file_name>");
  printf("\ninput file:");
  printf("\nN (number of polihedrons)");
  printf("\nK (number of faces of a polihedron)");
  printf("\nC[1][j] j=1..K");
  printf("\nC[2][j] j=1..K");
  printf("\n...");
  printf("\nC[N][j] j=1..K");
}//- - - - -help
 
 
 
    // Обнуляем массив перед заполнением
void initNetwork ( network_t network )
{
int i, j;
for(i=0; i<N_DIM; ++i ) 
  for(j=0; j<N_DIM; ++j ) 
    network[i][j] = 0;
}//- - - - - -initNetwork
 
void capPrint (  network_t network, char *title  )
{
int i,j;
 
printf("\n%s",title);
for(i=0; i<=sinkCode; ++i ) {
  printf("\n");
  for(j=0; j<=sinkCode; ++j ) {
    printf("%2d ",network[i][j]);
    }
  }//for i
}//- - - - -capPrint
 
    /* Чтение данных из файла:
     * N, K - два целых,
     * N раз (по числу многогранников)
     * по K целых чисел (по числу граней)
     * Смысл числа cap[i][j] - количество наклеек типа j наклеенных на многогранник i
     *   (разумеется нули тоже надо указывать)
     * Очевидно должны удовлеворятся условия
     *   1. Для каждого i cумма cap[i][j] по j == K (число граней многоранника)
     *   2. Для каждого j cумма cap[i][j] по i == K (число экземпляров наклеек одного типа)
     */  
void inputData( char *fileName )
{
int i,j;
FILE *inputFile;
inputFile = fopen(fileName,"r");
 
if ( inputFile==NULL) {
  printf("\nError opening file %s\n", fileName);
  myExit(1); 
  }
 
// Читаем из файла
fscanf(inputFile,"%d",&N);
fscanf(inputFile,"%d",&K);
if (N<0) { // Включает отладочную печать
  N=-N;
  myDebug = 1;
  }
 
 
initNetwork(cap);
sourceCode=0;   //код вершины-источника
sinkCode=2*N+1; //код вершины-стока
 
    // Пропускная способность дуг от источника к вершинам-К-гранникам 
for(i=1; i<=N; ++i ) cap[sourceCode][i]=K-1;
 
    // Пропускная способность дуг от вершинам-наклеек к стоку 
for(j=N+1; j<=2*N; ++j ) cap[j][sinkCode]=K-1;
 
for(i=1; i<=N; ++i ) {
  int faces=0;
  for(j=N+1; j<=2*N; ++j ) {
    int m;
    fscanf(inputFile,"%d",&m); 
    cap[i][j]=m;
    faces+=m;
    }//for j
  if (faces!=K) {// Для каждого i cумма cap[i][j] по j == K (число граней многоранника)
    printf("\nWrong number of stickers (%d instead of %d) for polihedron #%d",faces, K, i);
    myExit(1);
    }
  }//for i
 
for(j=N+1; j<=2*N; ++j ) {
  int stickers=0;
  for(i=1; i<=N; ++i ) stickers+=cap[i][j];
  if (stickers!=K) { // Для каждого j cумма cap[i][j] по i == K (число экземпляров наклеек одного типа)
    printf("\nWrong number of stickers (%d instead of %d) of type #%d",stickers, K, j-N);
    myExit(1);
    }
  }//for j
 
fclose(inputFile);  
}//- - - - -inputData
 
int pathLenOld;
 
 
    // Для каждого узла найти предыдущий на кратчайшем пути от источника в остаточной сети
void findPrevs ( )
{
int i, curNode;
    // Сначала номера предыдущих вершин неизвестны
for(i=0; i<=sinkCode; ++i ) prevNodes[i] = -1;
 
qInit(); // Инициализирует очередь для узлов
qPut(sourceCode); // Первым ставим в очередь источник
while (qLen()>0) {
  // Взять очередную вершину из очереди и обработать
  curNode = qGet();
 
  // Перебрать соседей очередной вершины в остаточной сети
  for(i=0; i<=sinkCode; ++i ) 
    if (rescap[curNode][i]>0 && prevNodes[i]<0) {
        // Если для соседа ещё не определена предыдущая вершина, 
        //   то назначаем предыдущей очередную вершину и помещаем соседа в очередь
      prevNodes[i] = curNode;
      qPut(i);
         // Если добрались до стока, то выходим из цикла
      if (i==sinkCode) break;
      }//if
  }//while
 
}//- - - - -findPrevs
 
 
    // Найти путь от источника до стока и его пропускную способность
    // узлы найденного пути поместим в очередь
int findPath ( void )
{
int pathCap; // пропускная способность найденного пути
int curNode, prevNode;
pathCap = N*K; // Пропускная способность не м.б. больше
qInit();
curNode = sinkCode;
qPut(curNode);
while (curNode!=sourceCode) {
  prevNode=prevNodes[curNode];
  if(pathCap>rescap[prevNode][curNode]) pathCap = rescap[prevNode][curNode];
  qPut(prevNode);
  curNode = prevNode;
  }//while
 
    // Длина кратчайшего от источника до стока в остаточной сети не может уменьшаться в ходе итераций
if ( qLen()<pathLenOld ) {
  printf("\nfindPrevs:Shortest path lenght decrease:%d<%d",qLen(),pathLenOld);
  }
 
pathLenOld=qLen();
 
return pathCap;
}//- - - - -findPath
 
 
    // Корректируем поток вдоль дуг, принадлежащих кратчайшему пути в остаточной сети
    //   на величину пропускной способности пути
void addCap ( int c )
{
int curNode, prevNode;
if(c<=0)  printf("\naddCap:error0");
curNode = qGet();
while (curNode!=sourceCode) {
  prevNode=qGet();
  if (cap[prevNode][curNode]>0) { // Дуга принадлежит сети, поток нужно увеличить
    flow[prevNode][curNode]+=c;
    if(flow[prevNode][curNode]>cap[prevNode][curNode])  printf("\naddCap:error1");
    }
  else if (cap[curNode][prevNode]>0) { // Противоположная дуга принадлежит сети, поток нужно уменьшить
    flow[prevNode][curNode]-=c;
    if(flow[prevNode][curNode]<0)  printf("\naddCap:error2");
    }
  else printf("\naddCap:error3");
  curNode=prevNode;
  }//while
}//- - - - -addCap
 
 
int main(int argc, char* argv[])
{
int i,j;
int numStep; // Число циклов увеличения потока
int pathCap;
char defInputFile[] = "input.txt";
myDebug = 0;
 
// Читаем исходные данные
if (argc<2) {
  printf("\nNo input file name in command line");
  help();
  inputData(defInputFile);
  //exit(1);
  }
else  inputData(argv[1]);
 
if (myDebug) {  capPrint(cap,"Network");}
    // Инициализируем нулевой поток
initNetwork(flow);
 
    // Цикл увеличения потока
    //   пока есть путь от источника до стока в "остаточной сети".
numStep=1;
pathLenOld=0;
while ( 1 ) {
  if (myDebug) {  
    printf ("\nIteration %d",numStep);
    capPrint(flow,"Flow");
    }
      // По исходной сети и текущему потоку строим вспомогательную сеть с "остаточной пропускной способностью".
  initNetwork(rescap);
  for(i=1; i<=N; ++i ) {
        // Обрабатываем дуги от источника до многогранников 
    rescap[sourceCode][i]=cap[sourceCode][i]-flow[sourceCode][i];
    rescap[i][sourceCode]=flow[sourceCode][i];
        // Обрабатываем дуги от многогранников до наклеек 
    for(j=N+1; j<=2*N; ++j ) {
      rescap[i][j]=cap[i][j]-flow[i][j];
      rescap[j][i]=flow[i][j];
      }//for j
    }//for i
 
        // Обрабатываем дуги от наклеек до стока 
   for(j=N+1; j<=2*N; ++j ) {
     rescap[j][sinkCode]=cap[j][sinkCode]-flow[j][sinkCode];
     rescap[sinkCode][j]=flow[sinkCode][j];
     }//for j
  if (myDebug) {  capPrint(rescap,"Res.network");}
 
        // Для сети с "остаточной пропускной способностью" строим сеть кратчайших путей от источника
    findPrevs();
        // Если для стока не найден предыдущий узел в остаточной сети, то
        // не сушествует увеличивающего пути от источника до стока, 
        // увеличение потока невозможно, выходим из цикла.
    if (prevNodes[sinkCode]<0) break;
 
        // Иначе по массиву предыдущих узлов строим кратчайший путь от стока до источника.
        //    и считаем пропускную способность найденного кратчайшего пути 
        //    Узлы пути помещаются в очередь
    pathCap = findPath();
    if (myDebug) { 
      printf("\nPath "); qPrint();
      printf("\nPress Enter");
      getc(stdin); // Нажать Enter
      }
 
        // Корректируем текущий поток на величину пропускной способности вдоль дуг, принадлежащих кратчайшему пути.
    addCap(pathCap);
 
    ++numStep;
 
}//while
 
    // Выводим результат - для каждого многогранника указываем номер типа наклейки, на которую нужно поставить многогранник.
printf("\n");
for ( i=1; i<=N; ++i ) {
  printf("\nPolyhedron %d",i);
  for ( j=1; j<=N; ++j ) 
    if(flow[i][j+N]+1==cap[i][j+N]) printf("  sticker type %d",j);
}
 
 
printf("\nPress Enter");
getc(stdin); // Нажать любой символ
return 0;
}//- - - - -main

Модуль с реализацией очереди
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
queue.c
 
int qArr[N_DIM];  // Массив для хранения элементов очереди
int 
  qHead, //Индекс первого элемента в очереди 
  qTail  //Индекс последнего элемента в очереди
  ;
 
    // Делаем очередь пустой
void qInit ( void )
{
  qHead = 0; //Индекс первого элемента в очереди 
  qTail = -1; //Индекс последнего элемента в очереди
}
 
    // Поместить элемент в очередь (в хвост)
void qPut ( int i )
{
  ++qTail;
  if(qTail>=N_DIM) {
    printf("\nqPut:queue overflow. qHead=%d; qTail=%d", qHead, qTail);
    myExit(1);
    }
  qArr[qTail] = i;
}
 
    // Элемент из головы очереди; удалить
int qGet ( void )
{
  return qArr[qHead++];
}
 
    // Длина учереди
int qLen ( void )
{
  return 1+qTail-qHead;
}
 
 
void qPrint ( void )
{
  int i;
  for (i=qHead;i<=qTail;++i) printf("%d,",qArr[i]);
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.01.2014, 01:36
Ответы с готовыми решениями:

Алгоритм Рабина-Карпа поиск строки в подстроке на Си
Помогите пожалуйста нужно сделать поиск подстроки в строке из файла с помощью алгоритма...

Поиск подстроки в строке: алгоритм Рабина-Карпа или Бойера-Мура(-Хорспула)
Необходимо реализовать алгоритм Рабина-Карпа или Бойера-Мура(-Хорспула), если нам дана подстрока,...

Алгоритм Рабина-Карпа
Всем привет. Почему у меня Алгоритм Рабина - Карпа работает только для подстроки которая входит...

Алгоритм Карпа-Рабина
В общем не могу понять почему не подсчитывает кол-во вхождений подстроки в строку. using System;...

Алгоритм Рабина-Карпа
Всем доброго времени суток! Имеется код Алгоритма Рабина-Карпа, поиск подстроки в строке. Сегодня...

1
kosichka-marlin
0 / 0 / 0
Регистрация: 02.01.2016
Сообщений: 1
07.01.2016, 18:58 2
Код верный, просто пример не от балды нужно брать. к примеру в файле input.txt
5
4
0 1 2 1 0
1 2 1 0 0
2 1 0 0 1
1 0 0 1 2
0 0 1 2 1
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.01.2016, 18:58

Алгоритм Рабина-Карпа
Необходимо написать программу на ассемблере которая будет выполнять поиск строки в тексте по...

(ищу алгоритм) Хопкрофта-Карпа
Люди, помогите пожалуйста. Есть у кого реализация алгоритма Хопкрофта-Карпа? Весь интернет излазил...

Алгоритм Рабина-Карпа, нужны комментарии к коду
Привет всем. Столкнулся с задачей разобраться с кодом алгоритма рабина карпа. Объясните пожалуйста...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru