Системы дорог

22.10.2009, 21:12. **Показов** 1958. **Ответов** 7

Студворк — интернет-сервис помощи студентам

Задана система двусторонних дорог. Найдите замкнутый путь длиной не более 100 км, проходящий через каждую дорогу ровно один раз.

Добавлено через 1 минуту
Плиз помогите мне((. Позарез нужно решение

Хотя бы идейку подкиньте мне

@ЛоРД_Оледжан · 22.10.2009, 21:34

1.Какая система?
2. Какую тему на данный момент изучаете?

22.10.2009, 21:44

Можно с помощью статистических данных, можно с помощью динамических. Желательно статиститические.

@Puporev · 22.10.2009, 22:00

В теорию графов рулите.

@odip · 23.10.2009, 21:33

Замкнутый путь через все дороги - это эйлеров цикл называется.
Задача найти эйлеров цикл с ограничением по длине.
Можно тупо искать перебором в глубину

Добавлено через 5 минут
Если не тупо - загляни в wikipedia - там и описания есть и алгоритм.
И может даже код есть.

@Krash · 21.12.2010, 21:57

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
//================ проверка связности =====================
 
//-----Проверка наличия вершин помеченных 2 маркером-------
char kolv2(int kolv,int mbuf[])
 {
  for (int i=0;i<kolv;i++)
   if (mbuf[i]==2)
    return 't';
  return 'f';
 }
//---------------------------------------------------------
 
char svaz(int kolv,int *gr[])
{
 int mbuf[maxkolv];
 
 for (int i=0;i<kolv;i++)
  mbuf[i]=1;
 
 mbuf[1]=2;
 while (kolv2(kolv,mbuf)=='t')
  for (i=0;i<kolv;i++)
   if (mbuf[i]==2)
    {
     mbuf[i]=3;
      for (int j=0;j<kolv;j++)
       if ((gr[i][j]==1)&&(mbuf[j]==1))
    mbuf[j]=2;
    };
 for (i=0;i<kolv;i++)
  if (mbuf[i]==1)
   return 'f';
 return 't';
}
//=========================================================
 
//================ поиск эйлерова пути ====================
 
//-----Проверка наличия ненулевых вершин ------------------
char kolvn0(int kolv,int mbuf[])
 {
  for (int i=0;i<kolv;i++)
   if (mbuf[i]>0)
    return 't';
  return 'f';
 }
//---------------------------------------------------------
 
void euler(int kolv,int *gr[])
{
 int v,u,i,x,i1=0,i2=0;
 int st1[maxkolv];
 int st2[maxkolv];
 
 for(i=0;i<kolv;i++) st1[i]=0, st2[i]=0;
 do
  cout<<"введите номер стартовой вершины: ",cin>>v; // ЗДЕСЬ В ЦИКЛЕ ПЕРЕБИРАЕМ ВСЕ ВЕРШИНЫ!!!
 while (v>kolv);
 
 st1[i1]=v;
 while (kolvn0(kolv,st1)=='t')
  {
   v=st1[i1];
   i=0;
   while ((i<kolv)&&(gr[v-1][i]==0))
    i++;
   if (i<kolv)
    {
     u=i;
     i1++;
     st1[i1]=u+1;
     gr[v-1][u  ]=0;
     gr[u  ][v-1]=0;
    }
   else
    {
     st2[i2]=st1[i1];
     st1[i1]=0      ;
     i1--;
     i2++;
    }
  };
 cout<<"эйлеров цикл: ";
 for(i=0;i<kolv-1;i++) cout<<st2[i]<<" -> ";
 cout<<st2[kolv-1];
 cout<<" -> "<<v;
}

@sashka32 · 11.04.2011, 14:25

Сообщение от Krash

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
//================ проверка связности =====================
 
//-----Проверка наличия вершин помеченных 2 маркером-------
char kolv2(int kolv,int mbuf[])
 {
  for (int i=0;i<kolv;i++)
   if (mbuf[i]==2)
    return 't';
  return 'f';
 }
//---------------------------------------------------------
 
char svaz(int kolv,int *gr[])
{
 int mbuf[maxkolv];
 
 for (int i=0;i<kolv;i++)
  mbuf[i]=1;
 
 mbuf[1]=2;
 while (kolv2(kolv,mbuf)=='t')
  for (i=0;i<kolv;i++)
   if (mbuf[i]==2)
    {
     mbuf[i]=3;
      for (int j=0;j<kolv;j++)
       if ((gr[i][j]==1)&&(mbuf[j]==1))
    mbuf[j]=2;
    };
 for (i=0;i<kolv;i++)
  if (mbuf[i]==1)
   return 'f';
 return 't';
}
//=========================================================
 
//================ поиск эйлерова пути ====================
 
//-----Проверка наличия ненулевых вершин ------------------
char kolvn0(int kolv,int mbuf[])
 {
  for (int i=0;i<kolv;i++)
   if (mbuf[i]>0)
    return 't';
  return 'f';
 }
//---------------------------------------------------------
 
void euler(int kolv,int *gr[])
{
 int v,u,i,x,i1=0,i2=0;
 int st1[maxkolv];
 int st2[maxkolv];
 
 for(i=0;i<kolv;i++) st1[i]=0, st2[i]=0;
 do
  cout<<"введите номер стартовой вершины: ",cin>>v; // ЗДЕСЬ В ЦИКЛЕ ПЕРЕБИРАЕМ ВСЕ ВЕРШИНЫ!!!
 while (v>kolv);
 
 st1[i1]=v;
 while (kolvn0(kolv,st1)=='t')
  {
   v=st1[i1];
   i=0;
   while ((i<kolv)&&(gr[v-1][i]==0))
    i++;
   if (i<kolv)
    {
     u=i;
     i1++;
     st1[i1]=u+1;
     gr[v-1][u  ]=0;
     gr[u  ][v-1]=0;
    }
   else
    {
     st2[i2]=st1[i1];
     st1[i1]=0      ;
     i1--;
     i2++;
    }
  };
 cout<<"эйлеров цикл: ";
 for(i=0;i<kolv-1;i++) cout<<st2[i]<<" -> ";
 cout<<st2[kolv-1];
 cout<<" -> "<<v;
}

При компилировании выдает кучу ошибок. Допиши плз или я что то не правильно делаю?

@Small Lamer · 11.04.2011, 21:46

Сообщение от sashka32

При компилировании выдает кучу ошибок. Допиши плз или я что то не правильно делаю?

Pascal
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
const
  maxn = 100;
var
  e,was:array[1..maxn,1..maxn]of longint;
  ne:array[1..maxn]of longint;
  stack:array[1..maxn*maxn]of longint;
  i,n,m,u,v,top,x,s:longint;
  ok:boolean;
 
begin
  readln(n,m);
  for i:=1 to m do begin
    readln(u,v,x);
    s:=s+x;
    inc(ne[u]); e[u,ne[u]]:=v;
    inc(ne[v]); e[v,ne[v]]:=u;
  end;
  if s<100 then begin write('No cycle');exit;end;
  for i:=1 to n do if ne[i] mod 2=1 then begin
    write('No cycle'); exit;
  end;
  writeln('Cycle:');
  top:=1; stack[1]:=1;
  while top>0 do begin
    u:=stack[top]; ok:=true;
    for i:=1 to ne[u] do begin
      v:=e[u,i];
      if was[u,v]=0 then begin
        inc(top); stack[top]:=v;
        was[u,v]:=1;was[v,u]:=1;
        ok:=false; break;
      end;
    end;
    if ok then begin
      dec(top);
      write(u,' ');
    end;
  end;
  readln;
end.

Новые блоги и статьи Все статьи Все блоги /
Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .
Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/

limon07

	Системы дорог 22.10.2009, 21:12. Показов 1958. Ответов 7 Метки нет (Все метки) Задана система двусторонних дорог. Найдите замкнутый путь длиной не более 100 км, проходящий через каждую дорогу ровно один раз. Добавлено через 1 минуту Плиз помогите мне((. Позарез нужно решение Хотя бы идейку подкиньте мне

@ЛоРД_Оледжан Программист 56 / 54 / 15 Регистрация: 23.07.2009 Сообщений: 336
	22.10.2009, 21:34
	1.Какая система? 2. Какую тему на данный момент изучаете? 0

limon07
	22.10.2009, 21:44
	Можно с помощью статистических данных, можно с помощью динамических. Желательно статиститические.

@Puporev Почетный модератор 64315 / 47611 / 32743 Регистрация: 18.05.2008 Сообщений: 115,167
	22.10.2009, 22:00
	В теорию графов рулите. 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	23.10.2009, 21:33
	Замкнутый путь через все дороги - это эйлеров цикл называется. Задача найти эйлеров цикл с ограничением по длине. Можно тупо искать перебором в глубину Добавлено через 5 минут Если не тупо - загляни в wikipedia - там и описания есть и алгоритм. И может даже код есть. 0