ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача на графы
15 сообщений из 40, страница 2 из 2
  2  все
Задача на графы
    #36258415
defrager
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
defrager
Гость
Не. 400млн простейших битовых операций выполнится секунды за 2 максимум.
...
Рейтинг: 0 / 0
19.10.2009, 00:09:56
| Ответить | Цитировать | Написать  
Задача на графы
    #36258629
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
Индийский (?) код с форума на порядки медленнее моего,
хотя технически он выглядит намного круче моего примитива:

Код: plaintext
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.
//============================================================================
// Name        : DAGCNT2.cpp
// Author      : Shaka
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#define MAXN  20000 
using namespace std;

typedef set<int> si;
typedef si::iterator sii;

si links[MAXN+ 1 ];
si vis[MAXN+ 1 ];
int w[MAXN+ 1 ];
bool incoming[MAXN+ 1 ], flag[MAXN+ 1 ];

void dfs(int v) {
   vis[v].insert(v);
   flag[v] =  1 ;
   for (sii i = links[v].begin(); i!=links[v].end(); i++) {
      int j = *i;
      if (!flag[j])
         dfs(j);
      for (sii p = vis[j].begin(); p!=vis[j].end(); p++)
         vis[v].insert(*p);
   }
}

int main() {
   freopen("E:\\C++\\SPOJ\\TestData\\4882in1.txt", "rt", stdin);
   freopen("E:\\C++\\SPOJ\\TestData\\999.txt", "wt", stdout);
   register int cas, N, M, i, j, s;
   scanf("%d", &cas);
   while (cas--) {
      scanf("%d %d", &N, &M);
      for (i =  1 ; i <= N; i++) {
         scanf("%d", w+i);
         links[i].clear();
         vis[i].clear();
      }
      memset(incoming, false, N+ 1 );
      while (M--) {
         scanf("%d %d", &i, &j);
         if (i!=j) {
            links[i].insert(j);
            incoming[j] =  1 ;
         }
      }
      memset(flag, false, N+ 1 );
      for (i =  1 ; i <= N; i++)
         if (!incoming[i])
            dfs(i);
      for (i =  1 ; i <= N; i++) {
         s =  0 ;
         for (sii k = vis[i].begin(); k != vis[i].end(); k++)
            s+=w[*k];
         printf("%d%c", s, i==N ? '\n' : ' ');
      }
   }
   return  0 ;
}

А вот, если в нем заменить сеты на битсеты? Может тогда он и уложится в тайм лимит.
...
Рейтинг: 0 / 0
19.10.2009, 09:31:20
| Ответить | Цитировать | Написать  
Задача на графы
    #36258685
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
> А вот, если в нем заменить сеты на битсеты? Может тогда он и уложится в тайм лимит.


Протупил.
Толку от этого будет 0 -- ведь в конце все равно придется
собирать суммы по всем финальным битсетам, а это главный тормоз.
Собственно главная часть кода работает 5с, а сбор сумм - 30с.
...
Рейтинг: 0 / 0
19.10.2009, 10:09:54
| Ответить | Цитировать | Написать  
Задача на графы
    #36259235
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
Пусть будет:
Код: plaintext
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.
/*
Как сабжевый бонус, код для определения
является ли данный ориентированный граф графом без циклов:
is_directed_acyclic_graph

Формат входного файла:
nv ne      <- число вершин (нумерация с 1) и число ор. ребер;
v1 v2      <- список "ne" штук ребер;
... ...
... ...
vN vM
*/

#include <ctime>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <bitset>
using namespace std;

#define NMX  20000       //-- макс. число вершин в графе;

int nv, ne, u, v, sch;
int b[NMX+ 1 ];
vector<int> p, q;
vector<int> d[NMX+ 1 ];
bitset<NMX+ 1 > c[NMX+ 1 ];


int main() {
    #define fp stdin
    //FILE* fp = fopen("E:\\C++\\SPOJ\\TestData\\is_dag_in.txt", "rt");

    clock_t begin = clock();
    fscanf(fp, "%d %d", &nv, &ne);

    for (int i =  1 ; i <= nv; ++i) {
        b[i] =  0 ;
        c[i].reset();
        d[i].clear();
    }

    for (int i =  1 ; i <= ne; ++i) {
        fscanf(fp, "%d %d", &u, &v);
        if (u == v) continue;
        if (!c[u].test(v)) {
            ++b[u];
            c[u].set(v);
            d[v].push_back(u);
        }
    }
    //fclose(fp);

    sch =  0 ;
    p.clear();
    for (int i =  1 ; i <= nv; ++i)
        if (b[i] ==  0 ) p.push_back(i);
    sch += (int)p.size();

    while (!p.empty()) {
        q.clear();
        for (int i =  0 ; i < (int)p.size(); ++i) {
            v = p[i];
            for (int j =  0 ; j < (int)d[v].size(); ++j) {
                --b[d[v][j]];
                if (b[d[v][j]] ==  0 ) q.push_back(d[v][j]);
            }
        }
        p.swap(q);
        sch += (int)p.size();
    }

    if (sch == nv) printf("YES, no cycles in the graph\n");
    else printf("NO, the graph has cycles\n");
    printf("Time = %.2f(s)\n", (double)(clock() - begin) / CLOCKS_PER_SEC);

    system("pause");
return  0 ;
}

NO WARRANTY IMPLIED
...
Рейтинг: 0 / 0
19.10.2009, 13:00:55
| Ответить | Цитировать | Написать  
Задача на графы
    #36259716
*SLOW*
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
*SLOW*
Гость
Народ! Помогите кто чем может! Как реализовать алгоритм поиска простых (НЕЭЙЛЕРОВЫХ И НЕГАМИЛЬТОНОВЫХ!)циклов в связном графе, состоящем из 1 компоненты связности? Или хотя бы как выглядит сам алгоритм?
...
Рейтинг: 0 / 0
19.10.2009, 15:01:51
| Ответить | Цитировать | Написать  
Задача на графы
    #36259847
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
*SLOW*Народ! Помогите кто чем может! Как реализовать алгоритм поиска простых (НЕЭЙЛЕРОВЫХ И НЕГАМИЛЬТОНОВЫХ!)циклов в связном графе, состоящем из 1 компоненты связности? Или хотя бы как выглядит сам алгоритм?
Обожди час-полтора и я тебе накодю очень коротенький код, который будет выводить все циклы
...
Рейтинг: 0 / 0
19.10.2009, 15:39:57
| Ответить | Цитировать | Написать  
Задача на графы
    #36260165
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
Пока так:
Код: plaintext
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.
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;

#define NMX  222 

int nv, ne;
int b[NMX];
vector<int> a[NMX];


void foo(int cur, int prev) {
    if (b[cur] ==  0 ) {
        b[cur] = prev;
        for (int i =  0 ; i < (int)a[cur].size(); ++i)
            if (a[cur][i] != prev)
                foo(a[cur][i], cur);
    }
    else {
        printf("%d ", cur);
        int j = prev;
        while (j != cur) {
            printf("%d ", j);
            j = b[j];
        }
        printf("\n");
    }
}


int main() {
    freopen("E:\\88.txt", "rt", stdin);
    freopen("E:\\99.txt", "wt", stdout);

    scanf("%d %d", &nv, &ne);

    for (int i =  1 ; i <= nv; ++i) {
        a[i].clear();
        b[i] =  0 ;
    }

    for (int i =  1 ; i <= ne; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        a[u].push_back(v);
        a[v].push_back(u);
    }

    foo( 1 ,  0 );

return  0 ;
}


88.txt
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
 5   7        -- 5 вершин,  7 неориентированных ребер;
 1   2 
 2   3 
 4   3 
 2   4 
 5   4 
 5   2 
 1   5


99.txt
Код: plaintext
1.
2.
3.
4.
5.
6.
 2   4   3  
 2   5   4   3  
 2   1   5   4   3  
 4   2   1   5  
 5   2   1  
 5   1         <<< ???         и не найден цикл ( 2 ,  4 ,  5 ) -- попозже посмотрю;
...
Рейтинг: 0 / 0
19.10.2009, 17:00:39
| Ответить | Цитировать | Написать  
Задача на графы
    #36260278
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
v.2
Код: plaintext
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.
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;

#define NMX  222 

int nv, ne;
int b[NMX];
vector<int> a[NMX];


void foo(int cur, int prev) {
    if (b[cur] ==  0 ) {
        b[cur] = prev;
        for (int i =  0 ; i < (int)a[cur].size(); ++i)
            if (a[cur][i] != prev)
                foo(a[cur][i], cur);
        b[cur] =  0 ;
    }
    else {
        printf("%d ", cur);
        int j = prev;
        while (j != cur) {
            printf("%d ", j);
            j = b[j];
        }
        printf("\n");
    }
}


int main() {
    freopen("E:\\88.txt", "rt", stdin);
    freopen("E:\\99.txt", "wt", stdout);

    scanf("%d %d", &nv, &ne);

    for (int i =  1 ; i <= nv; ++i) {
        a[i].clear();
        b[i] =  0 ;
    }

    for (int i =  1 ; i <= ne; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        a[u].push_back(v);
        a[v].push_back(u);
    }

    b[ 1 ] =  1 ;
    for (int k =  0 ; k < (int)a[ 1 ].size(); ++k)
        foo(a[ 1 ][k],  1 );

return  0 ;
}



Но теперь, за счет дублей, циклы плодятся как кролики:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
 2   4   3  
 2   5   4   3  
 1   5   4   3   2  
 2   3   4  
 2   5   4  
 1   5   4   2  
 2   3   4   5  
 2   4   5  
 1   5   2  
 1   2   3   4   5  
 4   2   3  
 5   2   3   4  
 1   2   4   5  
 4   3   2  
 5   2   4  
 1   2   5  
 2   4   3  
 5   4   3   2  
 2   3   4  
 5   4   2
...
Рейтинг: 0 / 0
19.10.2009, 17:31:44
| Ответить | Цитировать | Написать  
Задача на графы
    #36260423
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
Добавил через set< > пресечение вывода циклов-дубликатов:

Код: plaintext
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.
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

#define NMX  222 

typedef vector<int> cycle;
set<cycle> sc;

int nv, ne;
int b[NMX];
vector<int> a[NMX];


void foo(int cur, int prev) {
    if (b[cur] ==  0 ) {
        b[cur] = prev;
        for (int i =  0 ; i < (int)a[cur].size(); ++i)
            if (a[cur][i] != prev)
                foo(a[cur][i], cur);
        b[cur] =  0 ;
    }
    else {
        cycle p, q;
        p.push_back(cur);
        int j = prev;
        while (j != cur) {
            p.push_back(j);
            j = b[j];
        }
        q = p;
        sort(q.begin(), q.end());
        if (sc.count(q) !=  0 )
            return;
        sc.insert(q);
        for (int j =  0 ; j < (int)p.size(); ++j)
            printf("%d ", p[j]);
        printf("\n");
    }
}


int main() {
    freopen("E:\\88.txt", "rt", stdin);
    freopen("E:\\99.txt", "wt", stdout);

    scanf("%d %d", &nv, &ne);

    for (int i =  1 ; i <= nv; ++i) {
        a[i].clear();
        b[i] =  0 ;
    }

    for (int i =  1 ; i <= ne; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        a[u].push_back(v);
        a[v].push_back(u);
    }

    b[ 1 ] =  1 ;
    for (int k =  0 ; k < (int)a[ 1 ].size(); ++k)
        foo(a[ 1 ][k],  1 );

return  0 ;
}



Вроде нормально:

Код: plaintext
1.
2.
3.
4.
5.
6.
 2   4   3  
 2   5   4   3  
 1   5   4   3   2  
 2   5   4  
 1   5   4   2  
 1   5   2
...
Рейтинг: 0 / 0
19.10.2009, 18:15:07
| Ответить | Цитировать | Написать  
Задача на графы
    #36261767
defrager
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
defrager
Гость
Неужели так лень проверить?


int k = 1;
int w = 0;
int m[20000];

for (int i = 0; i < 20000; i++)
{
for (int j = 0; j < 20000; j++)
{
if (k & 1)
{
w += m[k];

}
}
}
даже debug версия выполнит это за 2-3 сеунды. Откуда 30.

RT183.1> А вот, если в нем заменить сеты на битсеты? Может тогда он и уложится в тайм лимит.


Протупил.
Толку от этого будет 0 -- ведь в конце все равно придется
собирать суммы по всем финальным битсетам, а это главный тормоз.
Собственно главная часть кода работает 5с, а сбор сумм - 30с.
...
Рейтинг: 0 / 0
20.10.2009, 12:58:24
| Ответить | Цитировать | Написать  
Задача на графы
    #36261794
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
Несколько неравноценная проверка же.
Доступ к биту идет через деление, вычисление остатка, смещение и битовую операцию.
Но если самому реализовать битсет, то этот цикл можно очень сильно ускорить.
...
Рейтинг: 0 / 0
20.10.2009, 13:07:19
| Ответить | Цитировать | Написать  
Задача на графы
    #36262099
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
> Неужели так лень проверить?


Так сто раз уже проверял. Разве можно как-то ускорить 2-й блок кода?
 
Код: plaintext
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.
#include <ctime>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <bitset>
using namespace std;

int read_ui() {
    int n =  0 ;
    char c;
    while (!isdigit(c = getchar()));
    while (isdigit(c)) {
        n = n *  10  + (c - '0');
        c = getchar();
    }
    return n;
}

const int nmx =  20001 ;

int tcs, nv, ne, u, v, ans;
int w[nmx];
int b[nmx];
vector<int> p, q;
vector<int> d[nmx];
bitset<nmx> z[nmx];
bitset<nmx> c[nmx];


int main() {
    freopen("E:\\C++\\SPOJ\\TestData\\4882in3.txt", "rt", stdin);
    freopen("E:\\C++\\SPOJ\\TestData\\999.txt", "wt", stdout);
    tcs = read_ui();
    while (tcs-- > 0) {

clock_t begin = clock();

        nv = read_ui();
        ne = read_ui();
        for (int i =  1 ; i <= nv; ++i) {
            w[i] = read_ui();
            b[i] =  0 ;
            c[i].reset();
            d[i].clear();
            z[i].reset();
            z[i].set(i);
        }

        for (int i =  1 ; i <= ne; ++i) {
            u = read_ui();
            v = read_ui();
            if (u == v) continue;
            if (!c[u].test(v)) {
                ++b[u];
                c[u].set(v);
                d[v].push_back(u);
            }
        }

        p.clear();
        for (int i =  1 ; i <= nv; ++i)
            if (b[i] ==  0 ) p.push_back(i);

        while (!p.empty()) {
            q.clear();
            for (int i =  0 ; i < (int)p.size(); ++i) {
                v = p[i];
                for (int j =  0 ; j < (int)d[v].size(); ++j) {
                    z[d[v][j]] |= z[v];
                    --b[d[v][j]];
                    if (b[d[v][j]] ==  0 ) q.push_back(d[v][j]);
                }
            }
            p.swap(q);
        }

printf("Time1 = %.2f\n", (double)(clock() - begin) / CLOCKS_PER_SEC);


--////////////////////////////////////////////////////////////////////
begin = clock();
        for (int i =  1 ; i <= nv; ++i) {
            ans =  0 ;
            for (int k =  1 ; k <= nv; ++k) if (z[i].test(k))
                ans += w[k];
            --////////printf("%d ", ans);
        }
printf("Time2 = %.2f\n", (double)(clock() - begin) / CLOCKS_PER_SEC);
--////////////////////////////////////////////////////////////////////

    }

return  0 ;
}




И вот такие времена:

Код: plaintext
1.
2.
Time1 =  5 . 26 
Time2 =  26 . 98
...
Рейтинг: 0 / 0
20.10.2009, 14:50:44
| Ответить | Цитировать | Написать  
Задача на графы
    #36262158
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
RT183.1Разве можно как-то ускорить 2-й блок кода?
Свой битсет, думаю, может очень сильно ускорить выполнение; наверное, примерно до тех самых 2-4 секунд defrager'а. Одно дело 400 млн. раз обратиться к произвольному биту, и совершенно другое -- упорядоченно их перебрать.
...
Рейтинг: 0 / 0
20.10.2009, 15:10:08
| Ответить | Цитировать | Написать  
Задача на графы
    #36262184
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
Для споджа этого все равно будет недостаточно, даже если второе время сделать нулем

У меня проц 1.6ГГц -- в 2 раза быстрее споджа + там 2 теста по 20000 вершин

Т.е. все мои времена надо как минимум умножать на 4
...
Рейтинг: 0 / 0
20.10.2009, 15:15:23
| Ответить | Цитировать | Написать  
Задача на графы
    #36262423
defrager
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
defrager
Гость
Странно. Не ожидал такого от bitset.

Вот кусок моего кода, который вручную биты проверяет в этой задаче

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
		for (int i =  0 ; i < N; i++)
		{
			if (i) printf(" ");
			
			int ans =  0 ;

			for (int j =  0 ; j <= p; j++)
			{
				int c = connected[i][j];

				for (int k =  0 ; k <  32 ; k++)
				{
					if (c &  1 )
					{
						ans += weight[(j <<  5 ) + k];
					}

					c >>=  1 ;
				}
			}
			printf("%d", ans);
		}
		printf("\n");
...
Рейтинг: 0 / 0
20.10.2009, 16:31:26
| Ответить | Цитировать | Написать  
15 сообщений из 40, страница 2 из 2
  2  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача на графы
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&gotonew=1&tid=1344166]:
 0ms
get settings:
 7ms
get forum list:
 15ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 230ms
get topic data:
 11ms
get first new msg:
 7ms
get forum data:
 3ms
get page messages:
 67ms
get tp. blocked users:
 1ms
others: 214ms
total:  561ms
созд. / загр.: 561ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]