Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

обход графа в ширину! - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Массив+кратность. найти ошибку. http://www.cyberforum.ru/cpp-beginners/thread73632.html
13. Îïðåäåëèòå â ïðîãðàììå ìàññèâ int m = {6, 17, 28, 7, 74, 29, 45, 3, 28, 8, 10, 87, 19, 9, 5, 28, 2, 59, 12, 31}; ïîñëå ÷åãî ïîäñ÷èòàéòå ñóììó âñåõ åãî ýëåìåíòîâ, êðàòíûõ ÷èñëó 3. #...
C++ Вычисление итерации. И ещё раз здравствуйте. Задачу, которую я собираюсь предложить, я, честно говоря, совсем не понял. Не как решать, а что, собственно, надо в ней делать. Задача в приклеплённом файле -- окно ответа не... http://www.cyberforum.ru/cpp-beginners/thread73629.html
C++ глючит ли VS08?видны приватные члены
у меня классе в приватах есть член а скажем..в меине когда пишу объект. - открывается меню с членами и методами и в меню виден член а,который приватный...это глюк?Оо
Произведение элементов массива, расположенных между максимальным и минимальным элементами C++
помогите мне разобраться с массивами. я работаю с программой MS Visual Studio 2008. не получается написать код программы. вот само задание. в одномерном массиве, состоящим из n элементов,...
C++ Запуск программы с параметром http://www.cyberforum.ru/cpp-beginners/thread73589.html
Люди, где собака зарыта? Не понимаю. #include <cstdlib> #include <stdio.h> #include <errno.h> #define BUF_SIZE 256 using namespace std; int main (int argc, char *argv )
C++ нужно написать очень легкий скрипт Помогите пожалуйста написать легкий скрипт, чтобы нажималась автоматом буква R 3 раза каждые 5 секунд постоянно подробнее

Показать сообщение отдельно
КсенияСергеевна
0 / 0 / 0
Регистрация: 07.09.2009
Сообщений: 45

обход графа в ширину! - C++

12.12.2009, 20:55. Просмотров 3078. Ответов 0
Метки (Все метки)

Здравствуйте!!
вот задание: "Задано прямоугольное клеточное поле и число k. Построить k различных непрерывных разрезов этого поля на два клеточных поля равной площади. "
мне препод примерно сказал как делать(обход графа в ширину,но соответственно не полного графа,а относительно моей задачи)
я написала код,по примеру, не особо разобралась!
помогите пожалуйста исправить ошибки!
и там не правильно rand написан,исправьте,пожалуйста!!

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
# include "stdafx.h"
# include <stdio.h> 
# include <alloc.h> 
# define SI sizeof (int)                       //элемент структуры смежности графа 
 
 
struct VER { int kol; int mv; int *adj; };     //число вершин
int n, h; 
struct VER *Vt;  
File *p, *f;  
 
 
 
 
 void vvod_graf ( ) 
 { 
 int i, j, N, kol; 
 p = fopen( "spisok_Adj.in", "r" );            
 if (fscanf (p, "%d", &n ) != EOF)             
 {
     h=n/2;
     Vt = (struct VER *) calloc (n, SI);       //выделение памяти основным элементам
     for ( i = 0; i < n; i++)                  //ввод метки вершины графа
     {  
         fscanf (p, "%d", &Vt [i] . mv ); 
         fscanf (p, "%d", &Vt [i] . kol ); 
         kol = Vt [i].kol;                      
         Vt [i] . adj = (int*) calloc (kol, SI); //выделение памяти списку смежности
 
         if (kol)
         { 
             for ( j = 0; j < kol; j++ )
             { 
                 fscanf (p, "%d", &N ); Vt [i]. adj [j] = N – 1; 
             } 
         } 
     } 
 } 
 fclose ( p ); 
 } 
 
 
 
 
  void Proverka ( int u ) 
  { 
      int i, v, flag = 1,l=0;
      Mark [u] = 2; 
      
      while (flag)
      {  
          for (i = 0; i < Vt [u ] . kol; i++)
          {  
              v = Vt [u ] . adj[i]; 
              
              if (Mark [v] = = 1)
              {
                  Mark [v] = 2;
                  l++;
              }
              else if (! Mark [v] ) 
                  Mark [v] = 1;
          }  
          
          for (i = 0; i < n && Mark [i] != 1; i++) ; 
          
          if (i == n)
              flag = 0; 
          else
          {
              u = i; 
              Mark [u] = 2;
          }
          
          if (l>=h) 
              flag = 0;
      } 
  }
 
 
 
void main ( void )
{ 
    int i, j, s, k, flag; 
    
    vvod_graf ( );
    Mark = (int*) calloc ( n, SI );         //выделение памяти под массив меток
    
    for ( i = 0; i < n; i++) 
        Mark [i] = 0;  
    
    printf ("\n Задайте K"); 
    scanf ( "%d", &k );
    
    for(j=0;j<=k;j++)
    { 
        s=rand(1,k);
        s --; 
        
        proverka ( s );                     // вывод результатов 
        
        f = fopen( "spisok.out", "w" ); 
        printf (f, "%d ", s+1 ); 
        printf (f, "\n" ); 
        
        for ( i = 0; i < n; i++ ) 
        { 
            if (i != s && ! Mark [i] ) 
                printf (f, "%d ", Vt [ i ] . mv); 
        } 
 
        printf (f, "\n"); 
        fclose ( f ); 
    }
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru