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

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

Восстановить пароль Регистрация
 
Dima2202
0 / 0 / 0
Регистрация: 12.05.2012
Сообщений: 6
13.05.2012, 18:28     Алгоритм цепочка (исправить код) #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 минут
моет просто ввод и вывод поменять?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.05.2012, 18:28     Алгоритм цепочка (исправить код)
Посмотрите здесь:

C++ Исправить код
C++ Помогите исправить алгоритм (есть код)
Помогите дописать( исправить код) алгоритм C++
исправить код C++
C++ Исправить код
Исправить код, реализующий алгоритм сортировки C++
C++ исправить код
C++ Алгоритм сортировки слиянием. Исправить ошибки в коде

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dima2202
0 / 0 / 0
Регистрация: 12.05.2012
Сообщений: 6
14.05.2012, 21:51  [ТС]     Алгоритм цепочка (исправить код) #2
кто-нибудь , просто отзовитесь .... ошибка типа...Strings not matched at line...в разных тестах разные линии , и что делать?
Yandex
Объявления
14.05.2012, 21:51     Алгоритм цепочка (исправить код)
Ответ Создать тему
Опции темы

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