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

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

Войти
Регистрация
Восстановить пароль
 
Ganya
0 / 0 / 0
Регистрация: 25.04.2013
Сообщений: 8
#1

задача ШКОЛЫ (описание внутри) - C++

25.04.2013, 02:36. Просмотров 471. Ответов 3
Метки нет (Все метки)

Школы
С целью подготовки к проведению олимпиады по информатике мэр решил обеспечить надежным электроснабжением все школы города. Для этого необходимо провести линию электропередач от альтернативного источника электроэнергии "ГРЭС" к одной из школ города (к какой неважно), а также соединить линиями электропередач некоторые школы между собой.
Считается, что школа имеет надежное электроснабжение, если она напрямую связана с источником " ГРЭС ", либо с одной из тех школ, которые имеют надежное электроснабжение. Известна стоимость соединения между некоторыми парами школ. Мэр города решил выбрать одну из двух наиболее экономичных схем электроснабжения (стоимость схемы равняется сумме стоимостей соединений пар школ).
Напишите программу, которая вычисляет стоимость двух наиболее экономных схем альтернативного электроснабжения школ.
Входные данные
В первой строке входного файла находятся два натуральных числа, разделенных пробелом: N (3≤N≤100), количество школ в городе, и M - количество возможных соединений между ними. В каждой из последующих M строк находятся по три числа: Ai, Bi, Ci, разделенных пробелами, где Ci - стоимость прокладки линии электроснабжения (1≤Ci ≤300) от школы Ai до школы Bi (i = 1, 2, ..., N).
Выходные данные
В единственной строке выходного файла должны содержаться два натуральных числа S1 и S2, разделенных пробелом - две наименьшие стоимости схем (S1 ≤ S2). S1=S2 тогда и только тогда, когда существует несколько схем надежного электроснабжения наименьшей стоимости.
Пример

input.txt

5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66

output.txt

110 121

помогите пожалуйста решить задачу, буду искренне благодарен!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.04.2013, 02:36     задача ШКОЛЫ (описание внутри)
Посмотрите здесь:

Ошибка описание внутри темы - C++
#include <stdio.h> #include <conio.h> #include <math.h> #include <iostream> int main (void) { setlocale(LC_ALL, "Russian");...

Расстояние от точки до луча (описание внутри) - C++
Помогите люди добрые :) Расстояние от точки до луча Даны координаты точки (x,y) и координаты начала и конца вектора (x1,y1) и (x2,y2). ...

Написать программу Изолированные города(Описание внутри) - C++
В государстве N городов с номерами 1.2….N. Некоторые города связаны между собой дорогами и образуют штат. Сколько штатов в государстве. ...

Задача на описание функции Power2(A, N) вещественного типа - C++
Описать функцию Power2(A, N) вещественного типа, находящую величину Aв степени N (A — вещественный, N — целый параметр) по следующим...

Задача на описание функции Leng(x_A, y_A, x_B, y_B) вещественного типа - C++
Описать функцию Leng(xA, yA, xB, yB) вещественного типа, находящую длину отрезка AB на плоскости по координатам его концов:|AB| =((x_a-x_b...

Задача на рекурсию - почему вроде бы ошибочный код внутри работает правильно? - C++
Изучаю учебник C++, решаю задачки в конце глав. В одной задачке надо было написать рекурсивную функцию, получающую в качестве...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ganya
0 / 0 / 0
Регистрация: 25.04.2013
Сообщений: 8
19.05.2013, 13:24  [ТС]     задача ШКОЛЫ (описание внутри) #2
ап
Ganya
0 / 0 / 0
Регистрация: 25.04.2013
Сообщений: 8
22.05.2013, 13:43  [ТС]     задача ШКОЛЫ (описание внутри) #3
ап
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.05.2013, 18:59     задача ШКОЛЫ (описание внутри)
Еще ссылки по теме:

Ученики школы С++ - C++
Сведения об ученике состоят из его имени и фамилии и названия класса (года обучения и буквы), в котором он учится. Дан файл f, содержащий...

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

Определить среднее количество участников олимпиады из одной школы - C++
На вход программе подаются сведения о номерах школ учащихся, участвовавших в олимпиаде. В первой строке сообщается количество учащихся N....

Сколько времени в минутах потратит ученик на дорогу от школы до стадиона, - C++
Помогите с задачей плиз))) Сколько времени в минутах потратит ученик на дорогу от школы до стадиона, если это расстояние составляет S...

Выяснить, сколько учеников школы не имеют отметок ниже четырех - C++
Дан файл f, содержащий те же сведения об учениках, фамилия имя класс буква, и дополнительно отметки, полученные учениками в последней...

Распечатать список учеников музыкальной школы, которые учатся играть на скрипке - C++
Распечатать список учеников музыкальной школы, которые учатся играть на скрипке. Указать также, сколько лет они занимаются музыкой и...


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

Или воспользуйтесь поиском по форуму:
ViktorKozlov
133 / 125 / 2
Регистрация: 13.12.2012
Сообщений: 293
22.05.2013, 18:59     задача ШКОЛЫ (описание внутри) #4
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
#include <climits>
#include <iostream>
using std::cout;
using std::endl;
 
#include <fstream>
using std::ifstream;
using std::ofstream;
 
int N,M;
bool *points;
int *ribsPointsOrigIndex;
bool firstCall=true;
int countSave;
ofstream output("output.txt");
 
int minPrice(int ribsPrice[], int ribsPoint1[], int ribsPoint2[])
{
    for (int i=0;i<N;i++)
        points[i]=false;
 
    int sum=0;
 
    points[0]=true;
    int count=N;
    int min,minpoint1,minpoint2,index;
    while (--count)
    {
        min=301;
        for (int i=0;i<M;i++)
        {
            if (points[ribsPoint1[i]-1]!=points[ribsPoint2[i]-1])
                if (ribsPrice[i]<min)
                {
                    min=ribsPrice[i];
                    minpoint1=ribsPoint1[i];
                    minpoint2=ribsPoint2[i];
                    index=i;
                }
        }
        if (min==301 && firstCall)
        {
            output<<"Error: impossible to connect the points";
            exit(0);
        }
        sum+=min;
        points[minpoint1-1]=true;
        points[minpoint2-1]=true;
 
        if (firstCall)
        {
            ribsPointsOrigIndex[countSave]=index;
            countSave++;
        }
    }
    
    return sum;
}
 
int main()
{
    ifstream input("input.txt");
    input>>N>>M;
 
    int* ribsPrice=new int[M];
    int* ribsPoint1=new int[M];
    int* ribsPoint2=new int[M];
    ribsPointsOrigIndex=new int[M];
 
    points=new bool[N];
 
    for (int i=0;i<M;i++)
    {
        input>>ribsPoint1[i]>>ribsPoint2[i]>>ribsPrice[i];
    }
 
    output<<minPrice(ribsPrice,ribsPoint1,ribsPoint2);
 
    firstCall=false;
    int min2=INT_MAX;
    for (int i=0;i<countSave;i++)
    {
        int index=ribsPointsOrigIndex[i];
        int buf1=ribsPoint1[index];
        int buf2=ribsPoint2[index];
        ribsPoint1[index]=101;
        ribsPoint2[index]=101;
        int minPriceRes=minPrice(ribsPrice,ribsPoint1,ribsPoint2);
        if (minPriceRes<min2)
            min2=minPriceRes;
        ribsPoint1[index]=buf1;
        ribsPoint2[index]=buf2;
    }
 
    output<<" "<<min2;
 
    input.close();
    output.close();
 
    delete[] ribsPrice;
    delete[] ribsPoint1;
    delete[] ribsPoint2;
    delete[] ribsPointsOrigIndex;
    delete[] points;
    return 0;
}
Yandex
Объявления
22.05.2013, 18:59     задача ШКОЛЫ (описание внутри)
Ответ Создать тему
Опции темы

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