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

Вывести количество идеальных вариантов - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ fscanf(stream,"%s",s) читает до первого пробела? http://www.cyberforum.ru/cpp-beginners/thread221726.html
как прочитать строку из текстового файла целиком? (до \n)
C++ Односвязный кольцевой список. Ребят, подскажите как реализовать односвязный кольцевой список с ключами. Без ключей я знаю как, а что делают эти самые ключи? http://www.cyberforum.ru/cpp-beginners/thread221725.html
кириллица C++
Подскажите, как сделать ,чтобы в Borland C вывод был русскими буквами. Я написал setlocale(LC_ALL, "Russian"); вывод стал на кириллице,а вот информацию которую вводишь - нет
Удаление из строки всех символов, коды которых попадают в заданный диапазон C++
написать функцию удаления из строки s всех символов ASCIIкоды которых попадают в диапозон от н1 до н2 включительно 0<=н1<=255,0<=н2<=255, н1<=н2 помогите!
C++ Блок схема http://www.cyberforum.ru/cpp-beginners/thread221712.html
Люди помогите! =( Написал программу на Паскале и не могу схему алгоритма начертить, запутываюсь постоянно..Нарисуйте кто может и залейте куда нибудь, оч прошу =). Вот программа: uses crt; var ...
C++ Построение центра дерева (графы) Задача состоит в том, что нужно найти центр дерева, и при этом алгоритм должен учитывать особенность графов этого типа (центр содержит одну или две смежные вершины). Пробовал через матрицу смежности... подробнее

Показать сообщение отдельно
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
30.12.2010, 18:05
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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
//////////////////////////////////////////////////////////////////////////////////////
//есть три множества одинаковой мощности-мужчины женщины и дома. (все по n)
//между мужчинами и женщинами есть симпатии.
//и мужчинам и женщинам нравятся некоторые дома.
//сколько обоюдносимпатизирующих пар можно заселить в нравящийся им дом?
//т.е. надо вывести кол-во идеальных вариантов.
//////////////////////////////////////////////////////////////////////////////////////
//Задача решена с помощью алгоритма Куна.
//////////////////////////////////////////////////////////////////////////////////////
#include <deque>
#include <iostream>
#include <map>
//////////////////////////////////////////////////////////////////////////////////////
typedef std::map<int, bool>       T_adj_row;
typedef std::map<int, T_adj_row>  T_adj_matr;
typedef std::deque<bool>          T_use;
typedef std::deque<int>           T_matching;
//////////////////////////////////////////////////////////////////////////////////////
T_adj_matr  input_bipartite_graph(int  couples_total)
{   
    T_adj_matr  adj_matr;
    const int   HOUSE_NUM_MIN  = 1;
    const int   BREAK_NUMBER   = HOUSE_NUM_MIN - 1;
    std::cout << "Для каждой пары мужчина-женщина введите "
              << "номера нравящихся им домов "
              << std::endl
              << "из диапазона "
              << HOUSE_NUM_MIN
              << ".."
              << couples_total
              << " ("
              << BREAK_NUMBER
              << " - конец ввода): "
              << std::endl;    
 
    for(int  couple_ind = 0; couple_ind < couples_total; ++couple_ind)
    {        
        std::cout << std::endl
                  << "Пара "                  
                  << couple_ind + 1
                  << ": "
                  << std::endl;
 
        std::cout << '\t'
                  << "номера нравящихся домов: "
                  << std::endl;
        
        for(;;)
        {
            std::cout << '\t'
                      << "-> ";
 
            int  house_ind = 0;
            std::cin >> house_ind;
            if(house_ind == BREAK_NUMBER)
            {
                break;
            }
            else if(   house_ind < HOUSE_NUM_MIN 
                    || couples_total < house_ind)
            {
                std::cout << '\t'
                          << "допустимы только номера из диапазона "
                          << HOUSE_NUM_MIN
                          << ".."
                          << couples_total
                          << std::endl;                          
            }
            else
            {
                house_ind += couples_total - 1;
                adj_matr[couple_ind][house_ind] = adj_matr[house_ind][couple_ind] = true;
            }
        }        
    }
    return  adj_matr;
}
//////////////////////////////////////////////////////////////////////////////////////
bool  find_matching
    (
        int          couple_ind,
        int          couples_total,
        T_use&       use_couple,
        T_adj_matr&  adj_matr,
        T_matching&  couple_of,
        int          empty_couple_ind
    )
{
    use_couple[couple_ind] = true;
    for(int  house_ind = couples_total; house_ind < couples_total * 2; ++house_ind)
    {
        if(!adj_matr[couple_ind][house_ind])  continue;
 
        if(                
               couple_of[house_ind] == empty_couple_ind 
           ||    !use_couple[couple_of[house_ind]]
              && find_matching
                     (
                         couple_of[house_ind],
                         couples_total,
                         use_couple,
                         adj_matr,
                         couple_of,
                         empty_couple_ind
                     )                  
          )
        {
            couple_of[house_ind] = couple_ind;
            return  true;
        }
    }
    return  false;
}
//////////////////////////////////////////////////////////////////////////////////////
void  print_couples_settling(int  couples_total, T_adj_matr&  adj_matr)
{
    const int   EMPTY_COUPLE_IND = -1;
    T_use       use_couple  (couples_total);                                            
                                            
    T_matching  couple_of   (couples_total * 2, EMPTY_COUPLE_IND);//Размер двойной, так как
                                                                  //номера домов начинаются
                                                                  //с couples_total.
    //Пробегаемся по парам:
    for(int  couple_ind = 0; couple_ind < couples_total; ++couple_ind)
    {
        //Обнуляем использованные вершины.
        use_couple.assign(couples_total, false);
        find_matching
            (
                couple_ind, 
                couples_total, 
                use_couple, 
                adj_matr, 
                couple_of,
                EMPTY_COUPLE_IND
            );
    }
 
    //Печатаем найденное максимальное паросочетание:
    std::cout << std::endl
              << "Максимальное паросочетание:"
              << std::endl;
    for(int  house_ind = couples_total; house_ind < couples_total * 2; ++house_ind)
    {
        if(couple_of[house_ind] != EMPTY_COUPLE_IND)
        {
            std::cout << '\t'
                      << "дом "
                      << house_ind - (couples_total - 1)
                      << " - пара "
                      << couple_of[house_ind] + 1
                      << std::endl;
        }
    }
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    std::cout << "Введите количество пар мужчина-женщина: ";
    int  couples_total = 0;
    std::cin >> couples_total;
 
    T_adj_matr  adj_matr(input_bipartite_graph(couples_total));
    print_couples_settling(couples_total, adj_matr);
}
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru