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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
lenston
2 / 0 / 1
Регистрация: 12.11.2014
Сообщений: 33
#1

Олимпиадная задача. Деревни - C++

12.11.2014, 20:51. Просмотров 915. Ответов 16
Метки нет (Все метки)

Всем привет.. задача такая:

Деревни
В тридесятом государстве есть N деревень. Некоторые пары деревень соединены дорогами. В целях экономии, «лишних» дорог нет, т.е. из любой деревни в любую можно добраться по дорогам единственным образом.
Новейшие исследования показали, что тридесятое государство находится в сейсмически опасной зоне. Поэтому глава государства захотел узнать, какой именно ущерб может принести его державе землетрясение. А именно, он хочет узнать, какое минимальное число дорог должно быть разрушено, чтобы образовалась изолированная от остальных группа ровно из P деревень такая, что из любой деревни из этой группы до любой другой деревни из этой группы по-прежнему можно будет добраться по неразрушенным дорогам (группа изолирована от остальных, если никакая неразрушенная дорога не соединяет деревню из этой группы с деревней не из этой группы).
Вы должны написать программу, помогающую ему в этом.
Формат входных данных
Первая строка входного файла содержит два числа: N и P (1≤P≤N≤150). Все остальные строки содержат описания дорог, по одному на строке: описание дороги состоит из двух номеров деревень (от 1 до N), которые эта дорога соединяет. Все числа во входном файле разделены пробелами и/или переводами строки.
Формат выходных данных
В выходной файл выведите единственное число – искомое количество дорог.

Примеры
3 2
1 2
3 2
ответ 1

11 6
1 2
1 3
1 4
1 5
2 6
2 7
2 8
4 9
4 10
4 11
ответ 2

Было найдено решение на паскале

Решение задачи на паскале:
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
41
42
43
44
45
46
47
48
49
50
Const
  MaxN=152;
  Infinity=200;
  
Var
  I,N,P,M:LongInt;
  Edge:Array[1..MaxN]Of Record A,B:LongInt; End;
  Min:Array[1..MaxN,1..MaxN]Of Byte;
  Visited:Array[1..MaxN]Of Boolean;
  Res:LongInt;
  
Procedure DFS(Start:LongInt);
Var
  I,J,K:LongInt;
  Next:LongInt;
  
Begin
    Visited[Start]:=True;
    FillChar(Min[Start],SizeOf(Min[Start]),Infinity);
    Min[Start][1]:=0;
    For I:=1 To M Do
        If (Edge[I].A=Start) Or (Edge[I].B=Start) Then Begin
            If Edge[I].A=Start Then Next:=Edge[I].B
            Else Next:=Edge[I].A;
        If Not Visited[Next] Then Begin
            DFS(Next);
            For J:=N DownTo 1 Do If Min[Start][J]<Infinity Then Begin
                For K:=1 To N Do
                    If Min[Next][K]<Infinity Then
                        If Min[Start][J+K]>Min[Start][J]+Min[Next][K] Then
                           Min[Start][J+K]:=Min[Start][J]+Min[Next][K];
            Inc(Min[Start][J]);
            End;
        End;
    End;
End;
 
Begin
  Read(N,P);
  For M:=1 to N-1 do
    Read(Edge[M].A,Edge[M].B);
  M:=N-1;
  FillChar(Visited,SizeOf(Visited),False);
  DFS(1);
  Res:=Min[1][P];
  For I:=2 To N Do
    If Min[I][P]+1<Res Then
      Res:=Min[I][P]+1;
  WriteLn(Res); 
End.

Нужно было переделать под C/C++

Решение задачи на C/C++:


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
#include <iostream>
#include <string.h>
using namespace std;
 
const int MaxN=152, Infinity=200;
 
struct Record {int A,B;};
Record Edge[MaxN];
 
int I,N,P,M,Res;
bool Visited[MaxN];
 
unsigned char Min[MaxN][MaxN];
 
void  DFS(int Start)
{
    int I,J,K,Next;
    Visited[Start]=true;
    memset(Min[Start],Infinity,sizeof(Min[Start]));
    Min[Start][1]=0;
    for (I=1; I==M; I++)
        if ((Edge[I].A==Start)||(Edge[I].B=Start)) {
            if (Edge[I].A==Start) Next=Edge[I].B;
            else Next=Edge[I].A;
        if (!Visited[Next]) {
            DFS(Next);
            for (J=N; J==1; J--) if (Min[Start][J]<Infinity) {
                for (K=1; K==N; K++)
                    if (Min[Next][K]<Infinity)
                        if (Min[Start][J+K]>Min[Start][J]+Min[Next][K])
                            Min[Start][J+K]=Min[Start][J]+Min[Next][K];
            ++(Min[Start][J]);
            }
        }
    }
}
 
int main()
{ 
    cin>>N>>P;
    for (M=1; M<N-1; M++) {
        cin>>Edge[M].A>>Edge[M].B;
    }
    M=N-1;
    memset(Visited,false,sizeof(Visited));
    DFS(1);
    Res=Min[1][P];
    for (I=2; I==N; I++) {
        if (Min[I][P]+1<Res)  Res=Min[I][P]+1;
    }
    cout<<endl<<Res; 
}
Но увы что-то пошло не так((
Программа выводит вместо ответа чиселко 200.. что есть неправильно..
Помогите, кто чем может..
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.11.2014, 20:51
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Олимпиадная задача. Деревни (C++):

Олимпиадная задача - C++
Вот наткнулся сегодня на такую задачу: Всем известно, что в позапрошлом веке ковбои занимались перегоном скота. Перегон скота всегда...

Задача на дп (олимпиадная) - C++
Здравствуйте, имеется данная задача, основная проблема состоит в том, что мое решение никак не проходит по времени. Пробовал писать через...

Олимпиадная задача - C++
Алфавит мурмарианской системы счисления включает три цифры - 1, 2 и 3. Одна из популярных социальных сетей &quot;НаМурмаре&quot; при регистрации...

Олимпиадная задача - C++
Есть такая задачка: В ряд выписаны числа, состоящие только из цифр 1, 3, 7: 1, 3, 7, 11, 13, 17, ... Необходимо по номеру N определить...

Олимпиадная задача - C++
Был в прошлом году на олимпиаде по программированию и там была такая задача: После запуска программы пользователь должен начать...

Олимпиадная задача - C++
Дошел до этой олимпиадной задачи и впал в ступор. Нагуглил, что можно решить с помощью матриц, либо с помощью графов, но какого-то...

16
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
12.11.2014, 21:10 #2
lenston, а можно в двух словах идею решения?
0
lenston
2 / 0 / 1
Регистрация: 12.11.2014
Сообщений: 33
12.11.2014, 21:20  [ТС] #3
Цитата Сообщение от Dani Посмотреть сообщение
а можно в двух словах идею решения?
решение на паскале было нагло скомунизженно с одного из сайтов.. как понял я там алгоритм дэйкстры.. причем процедура DFS вызывает сама себя.. как я понял, в проге перебираются все возможные варианты "отрезания пути")).. на паскале все отлично работает.. ответы верные.. а вот в сях что-то не так..
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
12.11.2014, 21:24 #4
чето я не вижу тут Дейкстры
0
lenston
2 / 0 / 1
Регистрация: 12.11.2014
Сообщений: 33
12.11.2014, 21:33  [ТС] #5
Цитата Сообщение от Dani Посмотреть сообщение
не вижу тут Дейкстры
Вывод, что тут алгоритм Дейстры, был сделан исходя из следующих кусков программы:

Pascal
1
2
3
Var
  Min:Array[1..MaxN,1..MaxN]Of Byte;
  Visited:Array[1..MaxN]Of Boolean;
Pascal
1
2
3
    Visited[Start]:=True;
    FillChar(Min[Start],SizeOf(Min[Start]),Infinity);
    Min[Start][1]:=0;
Pascal
1
  FillChar(Visited,SizeOf(Visited),False);
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
12.11.2014, 21:40 #6
три куска - объявление и задание значений массивам самого алгоритма не видно
0
lenston
2 / 0 / 1
Регистрация: 12.11.2014
Сообщений: 33
12.11.2014, 21:47  [ТС] #7
Цитата Сообщение от Dani Посмотреть сообщение
три куска - объявление и задание значений массивам самого алгоритма не видно
Согласись, массив с именем "посещенные" очень подходящий для Дейкстры.. и что в первую точку забивают значение ноль, а во все остальные, что-то похожее на бесконечность))..

//DAS кусок из WIKI
Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

Из этого можно сделать вывод, что прога основывалась на этом алгоритме))
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
12.11.2014, 21:58 #8
Цитата Сообщение от lenston Посмотреть сообщение
посещенные
посещенные также нужны и для DFS, который открыто используется в коде (функция с именем DFS)
1
Байт
Диссидент
Эксперт C
17225 / 11295 / 1789
Регистрация: 24.12.2010
Сообщений: 22,236
12.11.2014, 21:58 #9
lenston, С первого взгляда настораживает вот что. В Пасковском коде массивы нумеруются с 1 (Array[1..]) а в Си обязательно с 0. Обрати внимание на этот ньюанс.
0
lenston
2 / 0 / 1
Регистрация: 12.11.2014
Сообщений: 33
12.11.2014, 22:09  [ТС] #10
Цитата Сообщение от Dani Посмотреть сообщение
посещенные также нужны и для DFS, который открыто используется в коде (функция с именем DFS)
Не знал про этот метод)) а поискать не додумался)) ахаха..

Добавлено через 1 минуту
Цитата Сообщение от Байт Посмотреть сообщение
В Пасковском коде массивы нумеруются с 1 (Array[1..]) а в Си обязательно с 0
предлагаешь сделать все массивы [MaxN-1] ??

Добавлено через 2 минуты
Цитата Сообщение от Байт Посмотреть сообщение
В Пасковском коде массивы нумеруются с 1 (Array[1..]) а в Си обязательно с 0
или просто уменьшить MaxN на 1?

Добавлено через 4 минуты
Цитата Сообщение от Dani Посмотреть сообщение
функция с именем DFS
Этим, кстати, объясняется рекурсия))
0
Байт
Диссидент
Эксперт C
17225 / 11295 / 1789
Регистрация: 24.12.2010
Сообщений: 22,236
12.11.2014, 22:11 #11
Цитата Сообщение от lenston Посмотреть сообщение
предлагаешь сделать все массивы [MaxN-1] ??
Цитата Сообщение от lenston Посмотреть сообщение
или просто уменьшить MaxN на 1?
Это как желаешь. Главное - следи за индексами.
0
lenston
2 / 0 / 1
Регистрация: 12.11.2014
Сообщений: 33
12.11.2014, 23:42  [ТС] #12
Цитата Сообщение от Байт Посмотреть сообщение
С первого взгляда настораживает вот что. В Пасковском коде массивы нумеруются с 1 (Array[1..]) а в Си обязательно с 0. Обрати внимание на этот ньюанс.
Не помогло))

Добавлено через 1 час 29 минут

ВСЕ!! ПОЛУЧИЛОСЬ))
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
#include <iostream>
#include <string.h>
using namespace std;
 
const int  MaxN=153;
int Infinity=200;
 
int I,N,P,M;
struct Record {
    int A;
    int B;
    };
Record Edge[MaxN];
typedef unsigned char Byte;
Byte Min[MaxN][MaxN];
bool Visited[MaxN];
int Res;
  
void DFS(int Start)
{
    int I,J,K;
    int Next;
 
    Visited[Start]=true;
    memset(Min[Start],Infinity,sizeof(Min[Start]));
    Min[Start][1]=0;
    for (I=1; I<=M; I++) 
        if ((Edge[I].A==Start)||(Edge[I].B==Start)) {
            if (Edge[I].A==Start) Next=Edge[I].B;
            else Next=Edge[I].A;
        if (Visited[Next]!=true) {
            DFS(Next);
            for (J=N; J>=1; J--) if (Min[Start][J]<Infinity) {
                for (K=1; K<=N; K++) 
                    if (Min[Next][K]<Infinity) 
                        if (Min[Start][J+K]>Min[Start][J]+Min[Next][K])
                            Min[Start][J+K]=Min[Start][J]+Min[Next][K];
            Min[Start][J]++;
            }
        }
    }
}
 
 
int main()
{
  cin>>N>>P;
  for (M=1; M<N; M++) cin>>Edge[M].A>>Edge[M].B;
  M=N-1;
  memset(Visited,false,sizeof(Visited));
  DFS(1);
  Res=Min[1][P];
  for (I=2; I<=N; I++) {
    if (Min[I][P]+1<Res) Res=Min[I][P]+1;
  }
  cout<<Res; 
}
0
Байт
Диссидент
Эксперт C
17225 / 11295 / 1789
Регистрация: 24.12.2010
Сообщений: 22,236
13.11.2014, 00:13 #13
Цитата Сообщение от lenston Посмотреть сообщение
ВСЕ!! ПОЛУЧИЛОСЬ))
Ну что ж. Приятно, когда усилия потрачены не зря...
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4125 / 2256 / 560
Регистрация: 18.10.2014
Сообщений: 3,878
13.11.2014, 07:52 #14
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от lenston Посмотреть сообщение
Всем привет.. задача такая:
Можно решать следующим перебором (без DFS). Тупым, но не очень.

Согласно условию задачи, карта дорог представляет собой дерево на N вершинах, т.е. содержит ровно N-1 дорог. Изолированная связная группа из P вершин будет представлять собой поддерево исходного дерева из P вершин с ровно P-1 дорог.

Получаем алгоритм перебора - просто перебираем все возможные связные комбинации из P-1 ребер и вычисляем, сколько ребер ведет наружу из полученного поддерева. Минимальное количество ведущих наружу ребер - это и есть ответ задачи.

Вот моя реализация (использовались С++11 фичи, но не существенно). Выдает сколько дорог надо уничтожить, а также номера домов, которые войдут в изолированную группу, на которой был обнаружен этот минимум.

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
#include <cassert>
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>
#include <sstream>
 
using namespace std;
 
typedef pair<unsigned, unsigned> TEdge;
typedef vector<TEdge> TEdges;
typedef vector<unsigned> TEdgeSubset;
typedef set<unsigned> TVertexSet;
 
bool next_subset(TEdgeSubset &subset, unsigned n)
{
  unsigned overflow = n;
  auto it = subset.end();
 
  do
  {
    --it;
    if (++*it < overflow || it == subset.begin())
      break;
 
    --overflow;
  } while (true);
 
  assert(*it <= overflow);
  if (*it == overflow)
    return false;
 
  for (++it, ++overflow; it != subset.end(); ++it, ++overflow)
  {
    *it = *(it - 1) + 1;
    assert(*it < overflow);
  }
 
  return true;
}
 
int main()
{
  istringstream ss("11 6    1 2  1 3  1 4  1 5  2 6  2 7  2 8  4 9  4 10  4 11");
 
  // Read edges
  unsigned N, P;
  ss >> N >> P;
  assert(P <= N);
 
  TEdges edges;
 
  do
  {
    TEdge e;
    if (!(ss >> e.first >> e.second))
      break;
 
    assert(e.first > 0 && e.second > 0);
    --e.first;
    --e.second;
    assert(e.first < N && e.second < N);
    edges.push_back(e);
 
  } while (true);
 
  if (edges.size() < N - 1)
  {
    cout << "Invalid input data - disonnected village" << endl;
    return EXIT_FAILURE;
  }
 
  if (edges.size() > N - 1)
  {
    cout << "Invalid input data - excessive roads" << endl;
    return EXIT_FAILURE;
  }
 
  // Iterate
  unsigned min_degree = -1;
  TVertexSet min_vsubset;
 
  TEdgeSubset esubset(P - 1);
 
  { // Initial edge subset
    unsigned n = 0;
    generate(esubset.begin(), esubset.end(), [&n](){ return n++; });
  }
 
  do
  {
    // Generate vertex subset
    TVertexSet vsubset;
 
    for (unsigned i : esubset)
    {
      const TEdge &e = edges[i];
      vsubset.insert(e.first);
      vsubset.insert(e.second);
    }
 
    assert(vsubset.size() >= P);
    if (vsubset.size() > P)
      // Disconnected edges
      continue;
 
    // Calculate external degree
    unsigned degree = 0;
 
    for (const TEdge &e : edges)
      if ((vsubset.find(e.first) == vsubset.end()) != (vsubset.find(e.second) == vsubset.end()))
        ++degree;
 
    if (degree < min_degree)
    {
      min_degree = degree;
      min_vsubset = vsubset;
    }
 
  } while (next_subset(esubset, edges.size()));
 
  if (min_degree == -1)
    cout << "No solution" << endl;
  else
  {
    cout << "Destroy " << min_degree << " road(s)" << endl;
    cout << "Isolated houses: ";
    for (unsigned i : min_vsubset)
      cout << i + 1 << " ";
    cout << endl;
  }
 
  return 0;
}
Результат: http://ideone.com/I8Pfb7
2
lenston
2 / 0 / 1
Регистрация: 12.11.2014
Сообщений: 33
13.11.2014, 11:48  [ТС] #15
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Можно решать следующим перебором (без DFS). Тупым, но не очень.

Решение интересное.. Но проверить возможности нет, из-за отсутствия C++11.. ))

Добавлено через 1 минуту
Цитата Сообщение от lenston Посмотреть сообщение
нет, из-за отсутствия C++11.. ))
Пойду обновляться))
0
13.11.2014, 11:48
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.11.2014, 11:48
Привет! Вот еще темы с ответами:

Олимпиадная задача - C++
#include &lt;cstdio&gt; #include &lt;cstdlib&gt; #include &lt;iostream&gt; using namespace std; int main() { unsigned int N; cout&lt;&lt;&quot;N=&quot;;...

C++. Олимпиадная задача - C++
Здравствуйте! Код не проходит какой-то тест, может алгоритм не правильный. И если не правильный, то как исправить? Помогите найти ошибку....

Олимпиадная задача. Рыбаки - C++
Подскажите пожалуйста, как решается эта задача. Однажды N рыбаков отправились на рыбалку, где поймали X рыб. После этого рыбаки легли...

Сладкая олимпиадная задача - C++
Дан торт который порезан на m*n равных кусков и вы хотите иметь точно один фрукт на каждом куске. Давайте обозначим f(m,n) количество...


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

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

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