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

Задача с графом - C++

Восстановить пароль Регистрация
 
ExModE
2 / 2 / 2
Регистрация: 04.03.2011
Сообщений: 27
04.05.2014, 06:52     Задача с графом #1
Доброго дня всем, помогите решить задачу, (№75 на картинке), пожалуйста.
Кликните здесь для просмотра всего текста
[]http://cs618631.vk.me/v618631870/2286/aKJxHEYwIv0.jpg[/]

Подумал, может быть задача является типовой и существует некоторый алгоритм для ее решения, однако я ничего умнее, чем простой перебор не могу придумать, хотя даже его реализовать не в состоянии
orgraph.h:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct edge
{
    int vertex;
    edge * next;
};
 
struct orgraph
{
    int dibs;
    edge * childs;
    orgraph * next;
};
 
orgraph * getGraph(void);
orgraph.cpp
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
#include "orgraph.h"
#include <stdio.h>
 
orgraph *getGraph(void)
{
    FILE *input;
    if(fopen_s(&input, "input.txt", "r")) return nullptr;
    orgraph *head = nullptr, *current = nullptr;
    int n;
    fscanf_s(input, "%d", &n);
    if (n)
    {
        head = new orgraph;
        head->next = nullptr;
        fscanf_s(input, "%d", &(head->dibs));
        head->childs = nullptr;
        current = head;
        for (int i = 1; i < n; i++)
        {
            current->next = new orgraph;
            current = current->next;
            fscanf_s(input, "%d", &(current->dibs));
            current->next = nullptr;
            current->childs = nullptr;
        }
        int a, b;
        while (fscanf_s(input, "%d%d", &a, &b))
        {
            current = head;
            for (int i = 1; i < a; i++) current = current->next;
            if (current->childs)
            {
                edge * curedge = current->childs;
                while (curedge->next != nullptr) curedge = curedge->next;
                curedge->next = new edge;
                curedge = curedge->next;
                curedge->next = nullptr;
                curedge->vertex = b;
            }
            else
            {
                current->childs = new edge;
                current->childs->vertex = b;
                current->childs->next = nullptr;
            }
        }
    }
    fclose(input);
    return head;
}
 
int f(int k, orgraph* G)
{
    int counter = 0, numOfCurV=0, F=1;
    orgraph *current = G;
    
        while (current != nullptr)
        {
            numOfCurV++;
            int mink = -1;
            orgraph *cparent = G;
            while (cparent && F)
            {
                edge * curedge = cparent->childs;
                int isNotParent = 1;
                while (curedge && isNotParent)
                {
                    if (curedge->vertex == numOfCurV)
                    {
                        if (cparent->dibs <= k)
                        {
                            if (cparent->dibs < mink || mink == -1) mink = cparent->dibs;
                        }
                        else
                        {
                            F = 0;
                        }
                        isNotParent = 0;
                    }
                    else curedge = curedge->next;
                }
                cparent = cparent->next;
            }
            if (F) counter += mink;
            current == current->next;
        }
    }
    return counter;
}
 
void main()
{
    orgraph *g = getGraph();
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.05.2014, 06:52     Задача с графом
Посмотрите здесь:

C++ Задание графом
Работа с Ориентированным графом C++
C++ написать программу с графом
Работа с графом (Требуется по заявке клиента предложить способы обмена жилплощади) C++
C++ написать прогу с графом
C++ Алгоритм поиска пути в лабиринте, заданном связным графом

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 09:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru