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

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

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

Алгоритм цепочка (исправить код) - C++

13.05.2012, 18:28. Просмотров 517. Ответов 1
Метки нет (Все метки)

Условие

Задан набор неповторяющихся пар (Ai,Aj), где Ai, Aj принадлежат множеству А={A1,A2,…,An}. Необходимо составить цепочку максимальной длины по следующему правилу:
(Ai,Aj)+(Aj,Ak)=(Ai,Ak).
При образовании этой цепочки любая пара может быть использована не более одного раза.

Входные данные

Входные данные находятся в файле input.in. Первая строка этого файла содержит два числа: n – размер множества A (элементы множества целые числа от 1 до n) и k – количество различных пар. Следующие k строк файла содержат по два элемента через пробел, которые задают очередную пару..

Выходные данные

Выходной файл output.out содержит две строки: первая строка – длина цепочки максимальной длины, в следующей строке указаны пары (Ai,Aj) в той последовательности, в которой они участвовали при образовании цепочки максимальной длины. Если цепочек такой длины несколько, то выдается та из них, которая лексикографически меньше.

Пример входных данных

5 5
1 2
4 3
1 5
2 3
5 4


Пример выходных данных

3
1 5
5 4
4 3

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
#include <stdio.h>
#define MAX_N 18
 
long a[MAX_N][2],n,m,i,j,t,out,outk;
char d[(1<<MAX_N)-1][MAX_N];
char q[1<<(MAX_N/2)];
FILE *w;
 
void inputdata()
{
    FILE *f = fopen("input.in","rt");
    fscanf(f,"%ld%ld",&m,&n);
    for (i=0;i<n;++i) fscanf(f,"%ld%ld",&a[i][0],&a[i][1]);
    fclose(f);
}
 
char f(long a)
{
    return q[(a>>m)]+q[a & ((1<<m)-1)];
}
 
void force(long x,long y)
{
    if (x==0) return;
    force(x-(1<<y),d[x][y]-1);
    fprintf(w,"%ld %ld\n",a[y][0],a[y][1]);
}
 
void outputdata()
{
    w = fopen("output.out","wt");
    fprintf(w,"%ld\n",f(out));
    force(out,outk);
    fclose(w);
}
 
void main()
{
    inputdata();
    m=n/2+(n & 1);
    for (i=0;i<1<<n;++i)
    {
        for (j=0;j<m;++j)
            if (i & (1<<j)) q[i]++;
    }
    for (i=0;i<n;++i) d[1<<i][i]=n+1;
    for (i=1;i<1<<n;++i)
        for (j=0;j<n;++j)
             if (d[i][j])
             {
                for (t=0;t<n;++t)
                    if ((i & (1<<t))==0 && (a[j][1]==a[t][0]))  
                        if (!d[i | (1<<t)][t]) d[i | (1<<t)][t]=j+1;
                if (f(i)>f(out))
                {
                    out=i;
                    outk=j;
                }
             }
    outputdata();
}
Добавлено через 20 часов 55 минут
моет просто ввод и вывод поменять?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.05.2012, 18:28
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм цепочка (исправить код) (C++):

Помогите дописать( исправить код) алгоритм - C++
Условие Некоторые компании являются совладельцами других компании, так как приобрели часть их акций. Говорят, что компания А...

Помогите исправить алгоритм (есть код) - C++
Я приблизительно представляю алгоритм, но не так что бы написать код. Вот условие задачи: Высота стены N, ширина M длина рулона K, а...

Исправить код, реализующий алгоритм сортировки - C++
Доброе утро. Сделал попытку реализовать функцию сортировки простым двухпутевым слиянием, но не вышло. При запуске происходит ошибка,...

Алгоритм сортировки слиянием. Исправить ошибки в коде - C++
#include &lt;iostream&gt; #include &lt;time.h&gt; void merge(int array, int left, int right, int n) { int middle, start1, start2, j; ...

Рекурсивный алгоритм для вычисления выражения. Исправить ошибки в коде - C++
Доброго времени суток. Задача стоит такова: составить рекурсивны ...

Исправить код - C++
#include &lt;iostream&gt; #include &lt;fstream&gt; using namespace std; int main() { int le = 0; int re = 0; char a;

1
Dima2202
0 / 0 / 0
Регистрация: 12.05.2012
Сообщений: 6
14.05.2012, 21:51  [ТС] #2
кто-нибудь , просто отзовитесь .... ошибка типа...Strings not matched at line...в разных тестах разные линии , и что делать?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.05.2012, 21:51
Привет! Вот еще темы с ответами:

исправить на код С - C++
Здравствуйте, исправте пожалуйста программу на код С, кто может. Условие:Даны натуральное число n, действительные числа Х1,...,Хn(n&gt;=2)....

Исправить код - C++
void main () { const int size= 10; int a; srand(time(NULL)); for (int i = 0; i &lt; size; i++) a = rand() % 11 - 5; for...

Исправить код - C++
Здравствуйте, я решал задачу: Предположим, что уже построен и задан указателем P двунаправленный список, элементами которого являются...

Исправить код - C++
Компилятор выдает ошибку #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; int _tmain(int...


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

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

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