С Новым годом! Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.64/11: Рейтинг темы: голосов - 11, средняя оценка - 4.64
cezar12

Зaдача на графы с тимуса 1358

21.12.2010, 19:36. Показов 2269. Ответов 2
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Уже который день пытаюсь решить, подскажите алгоритм, вроде бы 26% это не много.
http://acm.timus.ru/problem.aspx?space=1&num=1358
Лучшие ответы (1)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
21.12.2010, 19:36
Ответы с готовыми решениями:

Зaдача на работу со строками.
Есть строка в которой есть хотя бы одна точка. Преобразовать так: удалив все запятые предшествующие точке, и заменить знаком "+"...

Зaдача на проверку условия
http://i040.***********/1102/b3/e94810696b12.jpg Решите пожалуйста г,д. (Натуральные числа задавать одномерным массивом)

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

2
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
21.12.2010, 21:23
вроде бы 26% это не много
- лучше бы больше было (это процент зачтеных решений, а не процент сложности).
А задача не очень сложная.
Вот из условия:
Сеть является связной, т.е. любые два компьютера соединены некоторой последовательностью проводов.
N — число компьютеров (1 ≤ N ≤ 1000). Далее идет N−1 строчка, в каждой из которых находится два числа ai, bi — номера компьютеров, которые нужно соединить проводом (1 ≤ ai, bi ≤ N).
Это значит, что сеть является простой цепочкой.
Задача будет заключаться в том, что найти любой конец этой цепочки и далее перебирать попорядку (по цепи) все компьютеры. Координаты можно присваивать этим компьютерам так:
-1000 0
-998 0
-996 0
и т.д.
0
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
22.12.2010, 08:16
Лучший ответ Сообщение было отмечено как решение

Решение

Немного ошибся вот в этом:
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Это значит, что сеть является простой цепочкой.
Вернее будет то что в графе нет ни одного замкнутого цикла.
В общем если коротко то вот что нужно для решения: Поиск в ширину.
Разместить вершины так, как в приложенном Doc1.


В общем вот принятый код:
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>
int main()
{
   int j, i, N, **mas, temp1, temp2, **mas_res, *mas_met, *q, q_st=0, q_end=1;
   std::cin >>N;
   mas=new int*[N];
   mas_res=new int*[N];
   mas_met=new int[N];
   q=new int[N];
   for(i=0; i<N; i++)
   {
       mas_met[i]=-1;
       mas_res[i]=new int[2];
       mas[i]=new int[N];
       for(j=0; j<N; j++)
           mas[i][j]=0;
   }
   for(i=0; i<N-1; i++)
   {
       std::cin>>temp1>>temp2;
       mas[temp1-1][temp2-1]=mas[temp2-1][temp1-1]=1;
   }
   q[0]=0; mas_met[0]=0;
   while(q_end<N)
   {
       for(i=0; i<N; i++)
           if(mas[q[q_st]][i]==1 && mas_met[i]==-1)
           {
               q[q_end++]=i; mas_met[i]=mas_met[q[q_st]]+1;
           }
       q_st++;
   }
   temp1=-1000; i=0;
   int temp=0;
   while(i<N)
   {
       temp2=-1000;
       while(i<N && temp==mas_met[q[i]])
       {
           mas_res[q[i]][0]=temp1;
           mas_res[q[i]][1]=temp2;
           temp2+=2;
           i++;
       }
       temp1+=2;
       temp++;
   }
   for(i=0; i<N; i++)
       std::cout<<mas_res[i][0]<<" "<<mas_res[i][1]<<std::endl;
 
   return 0;
}
Вложения
Тип файла: doc Doc1.doc (23.5 Кб, 47 просмотров)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
22.12.2010, 08:16
Помогаю со студенческими работами здесь

Самая сложная зaдача по c++ в мире
Здрасьте, мне препод по программированию задал написать задачу с функцией join , которая будет соединять две строки, которые надо будет...

Advanced зaдача о бракованных деталях
Привет всем! Неделю сражаюсь с одной задачкой для дисера, никак не могу одолеть... Вобщем есть у Вентцеля типовая задачка о бракованных...

Зaдача основана на великой теореме ФЕРМА
Задали написать программу на вижуал бейсик или Qbasic.Суть программы: есть формула X^n + Y^n = Z^n (может кто не вкурсе то ^n означает в...

задача с Тимуса
Добрый День!!! Помогите Пожалуйста написать код к задаче с Тимуса: http://acm.timus.ru/problem.aspx?space=1&amp;num=1826 Задача нужна на...

задача с Тимуса
http://acm.timus.ru/problem.aspx?space=1&amp;num=1123 Задача на зачет нужна :scratch:


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Новые блоги и статьи
сукцессия микоризы: основная теория в виде двух уравнений.
anaschu 11.01.2026
https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/
WordPad для Windows 11
Jel 10.01.2026
WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
Classic Notepad for Windows 11
Jel 10.01.2026
Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает?
Neotwalker 09.01.2026
В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
Модель микоризы: классовый агентный подход 3
anaschu 06.01.2026
aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR
ФедосеевПавел 06.01.2026
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .
Модель микоризы: классовый агентный подход 2
anaschu 06.01.2026
репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .
Расчёт токов в цепи постоянного тока
igorrr37 05.01.2026
/ * Дана цепь постоянного тока с сопротивлениями и источниками (напряжения, ЭДС и тока). Найти токи и напряжения во всех элементах. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru