ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача на графы
25 сообщений из 40, страница 1 из 2
  1  все
Задача на графы
    #36238442
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
Дан ориентированный ациклический граф.
Каждой его вершине приписан некий вес.
Надо для каждой вершины найти сумму весов вершин, в которые можно попасть
из данной вершины (включая в сумму и вес самой этой вершины). Пример:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
 4   4   -- 4 вершины, 4 ребра
 450   379   230   520   -- веса вершин (нумерация вершин с 1) 
 3   4   -- ребра (из №3 можно попасть в №4)
 2   4   --
 2   3   --
 2   4   --

Oтвет:
 450   1129   750   520 

Ограничения:
число_вершин <=  20000 
число_ребер <=  500000

Что-то не соображу как действовать.
Я накарябал абсолютно верное решение, но оно медленное, а надо быстрое.
Код: 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.
#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;
}

int tcs, nv, ne, u, v;
bool b[ 20005 ];
int w[ 20005 ];
int t[ 20005 ];
vector<int> d[ 500005 ];
bitset< 20005 > z[ 20005 ];
bitset< 20005 > c[ 20005 ];
bitset< 20005 > o;

int main() {
    freopen("E:\\C++\\SPOJ\\TestData\\88.txt", "rt", stdin);
    freopen("E:\\C++\\SPOJ\\TestData\\99.txt", "wt", stdout);
    o.reset();
    tcs = read_ui();            -------- // число тест-кейсов (в каждом тест-кейсе свой, новый граф)
    while (tcs-- > 0) {
        nv = read_ui();
        ne = read_ui();
        for (int i =  1 ; i <= nv; ++i) t[i] =  0 ;
        for (int i =  1 ; i <= nv; ++i) {
            w[i] = read_ui();
            b[i] = false;
            c[i].reset();
            d[i].clear();
            z[i].reset();
            z[i].flip(i);
        }

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

        int sch =  0 ;

        while (sch < nv) {
            for (int i =  1 ; i <= nv; ++i) {
                if (!b[i] && c[i] == o) {
                    b[i] = true;
                    for (int j =  0 ; j < (int)d[i].size(); ++j) {

                        z[d[i][j]] = z[d[i][j]] |= z[i];

                        c[d[i][j]].flip(i);

                    }

                    ++sch;
                }
            }
        }

        for (int i =  1 ; i <= nv; ++i)
            for (int k =  1 ; k <= nv; ++k) if (z[i].test(k))
                t[i] += w[k];

        for (int i =  1 ; i < nv; ++i) printf("%d ", t[i]);
        printf("%d\n", t[nv]);

    }

return  0 ;
}
...
Рейтинг: 0 / 0
07.10.2009, 20:20:20
| Ответить | Цитировать | Написать  
Задача на графы
    #36238461
Фотография 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.
--Input:

 2   --число тест-кейсов

 4   3 
 510   713   383   990 
 4   1 
 4   2 
 2   1 

 6   4 
 450   379   230   520   6   7 
 3   4 
 2   4 
 2   3 
 2   4 


--Ответ:

 510   1223   383   2213 
 450   1129   750   520   6   7
...
Рейтинг: 0 / 0
07.10.2009, 20:39:52
| Ответить | Цитировать | Написать  
Задача на графы
    #36238468
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
я надеялся что высокоскоростной bitset вытянет по времени, аж хренушки
...
Рейтинг: 0 / 0
07.10.2009, 20:44:38
| Ответить | Цитировать | Написать  
Задача на графы
    #36238511
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
RT183.1 пишет:

> Надо для каждой вершины найти сумму весов вершин, в которые можно попасть
> из данной вершины (включая в сумму и вес самой этой вершины). Пример:

Обход графа поиском в грубину (или в ширину, не помню какой даёт
список достижимости из данной вершины), получаешь список достижимых
вершин, потом по нему считаешь сумму весов.
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
07.10.2009, 21:12:48
| Ответить | Цитировать | Написать  
Задача на графы
    #36238600
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
Эх...
...
Рейтинг: 0 / 0
07.10.2009, 23:09:05
| Ответить | Цитировать | Написать  
Задача на графы
    #36238960
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
RT183.1Эх...
Не эх. А ох! Постановочки на spoj пошли какие-то простенькие.
...
Рейтинг: 0 / 0
08.10.2009, 09:46:30
| Ответить | Цитировать | Написать  
Задача на графы
    #36239152
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
maytonRT183.1Эх...
Не эх. А ох! Постановочки на spoj пошли какие-то простенькие.
дело не в решении самом по себе (мой код в моем первом посте всё прекрасно решает),
а в быстром, максимально быстром, решении. И вот я что-то не соображу что, как и куда.
...
Рейтинг: 0 / 0
08.10.2009, 11:01:58
| Ответить | Цитировать | Написать  
Задача на графы
    #36256252
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
junior idiot, я написал генератор теста для DAGCNT2:
Код: 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.
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <bitset>
using namespace std;

const int n =  20000 ;
const int m =  500000 ;
int tcs =  1 ;
bitset<n +  1 > a[n +  1 ];

int randint(int lt, int rt) {
    return lt + (int)((rt - lt) * (double)rand() / RAND_MAX + 1E- 15 );
}

int main() {
    freopen("E:\\4882in.txt", "wt", stdout);
    printf("%d\n", tcs);
    while (tcs-- > 0) {
        printf("%d %d\n", n, m);
        for (int i =  1 ; i < n; ++i) printf("%d ", randint( 1 ,  1000 ));
        printf("%d\n", randint( 1 ,  1000 ));
        for (int i =  1 ; i <= n; ++i) {
            a[i].reset();
            a[i].flip(i);
        }
        int cnt =  0 ;
        while (cnt < m) {
            int i = randint( 1 , n);
            int j = randint( 1 , n);
            if (!a[i].test(j)) {
                a[j] = a[j] |= a[i];
                printf("%d %d\n", i, j);
                ++cnt;
            }
        }
    }

return  0 ;
}
это ужасно -- мой код не знаю сколько времени будет обрабатывать этот тест (я не дождался)
...
Рейтинг: 0 / 0
16.10.2009, 16:14:04
| Ответить | Цитировать | Написать  
Задача на графы
    #36256277
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
RT183.1,
Да, я уже тоже свой код на рандомном графе гонял. Никакие более или менее общие алгоритмы замыкания графа у меня даже близко к нужному времени подогнать не получилось.
Более того, вот этот цикл
Код: plaintext
1.
2.
3.
        for (int i =  1 ; i <= nv; ++i)
            for (int k =  1 ; k <= nv; ++k) if (z[i].test(k))
                t[i] += w[k];
у меня уже сам по себе превышал time limit.
...
Рейтинг: 0 / 0
16.10.2009, 16:21:45
| Ответить | Цитировать | Написать  
Задача на графы
    #36256315
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
> Никакие более или менее общие алгоритмы замыкания графа у меня даже близко к нужному времени ...

Теперь понятно, почему Blue Mary благоразумно "игнорит" эту таску.
...
Рейтинг: 0 / 0
16.10.2009, 16:38:40
| Ответить | Цитировать | Написать  
Задача на графы
    #36257431
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
junior idiot,
долго (на самом деле бесконечно) считало из-за дичайших непоняток.
Цикл while(!p.empty()) почему-то обрывается преждевременно.
В b[i] я храню число ребер, исходящих из вершины i.
На каждой итерации я заполняю вектор "p" вершинами, из которых (уже)
ничего не исходит (а только входит).

Код: 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.
#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, sch;
int w[nmx];
int t[nmx];
int b[nmx];
vector<int> p;
vector<int> d[nmx];
bitset<nmx> z[nmx];
bitset<nmx> c[nmx];


int main() {
    freopen("E:\\C++\\SPOJ\\TestData\\4882in2.txt", "rt", stdin);
    freopen("E:\\C++\\SPOJ\\TestData\\4882out.txt", "wt", stdout);
    tcs = read_ui();
    while (tcs-- > 0) {
        nv = read_ui();
        ne = read_ui();
        for (int i =  1 ; i <= nv; ++i) {
            w[i] = read_ui();
            t[i] =  0 ;
            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 (!c[u].test(v)) {
                ++b[u];
                c[u].set(v);
                d[v].push_back(u);
            }
        }


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


        while (!p.empty()) {
            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]];
                }
            }

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


        //output:
        for (int i =  1 ; i <= nv; ++i)
            for (int k =  1 ; k <= nv; ++k) if (z[i].test(k))
                t[i] += w[k];
        for (int i =  1 ; i < nv; ++i) printf("%d ", t[i]);
        printf("%d\n", t[nv]);

        printf("sch = %d\n", sch);

    }

return  0 ;
}



Входной файл:

Код: 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.
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.
 1 
 50   150 
 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1 
 1   28 
 10   40 
 29   24 
 18   44 
 41   37 
 9   43 
 35   26 
 15   1 
 5   18 
 8   9 
 49   22 
 6   1 
 1   19 
 27   28 
 9   33 
 23   18 
 3   30 
 39   40 
 26   15 
 43   36 
 47   46 
 27   7 
 23   12 
 43   11 
 39   42 
 30   20 
 14   15 
 42   2 
 19   5 
 34   3 
 1   46 
 29   34 
 42   36 
 24   11 
 37   23 
 23   47 
 37   6 
 30   19 
 37   30 
 29   18 
 8   12 
 21   40 
 26   49 
 37   17 
 9   33 
 25   4 
 35   25 
 8   47 
 7   45 
 34   15 
 21   4 
 48   34 
 8   43 
 41   29 
 10   9 
 41   24 
 8   25 
 36   20 
 14   28 
 34   38 
 36   24 
 7   19 
 41   2 
 26   33 
 21   6 
 47   46 
 27   17 
 24   19 
 42   16 
 23   14 
 49   15 
 37   28 
 10   38 
 42   20 
 25   44 
 2   49 
 29   3 
 27   10 
 42   31 
 33   10 
 42   7 
 16   47 
 15   17 
 7   36 
 41   35 
 13   8 
 1   3 
 40   42 
 11   6 
 6   23 
 37   34 
 27   4 
 22   10 
 35   15 
 22   12 
 29   27 
 31   8 
 25   48 
 35   46 
 10   17 
 9   49 
 23   49 
 5   31 
 5   22 
 46   3 
 44   15 
 12   38 
 21   10 
 31   30 
 30   32 
 42   41 
 31   36 
 28   19 
 10   37 
 28   45 
 12   10 
 30   35 
 29   18 
 25   4 
 37   30 
 31   34 
 40   8 
 29   43 
 45   31 
 36   3 
 33   48 
 16   28 
 15   9 
 42   37 
 8   17 
 27   22 
 21   15 
 23   25 
 8   16 
 37   16 
 41   47 
 43   36 
 15   47 
 7   4 
 39   26 
 30   47 
 4   43 
 33   16 
 6   25 
 12   15 
 46   28 
 33   6 
 25   19 
 25   39 
 25   19


И вот такой дурацкий выход:

Код: plaintext
1.
2.
 1   1   1   1   1   1   1   2   1   3   1   2   1   1   2   1   1   1   1   1   1   1   1   1   1   1   2   1   1   3   1   1   1   2   1   2   2   1   1   1   1   2   1   1   1   1   1   1   1   1 
sch =  5

Я ничего не понимаю.
...
Рейтинг: 0 / 0
17.10.2009, 21:01:50
| Ответить | Цитировать | Написать  
Задача на графы
    #36257447
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
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.
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.
 1 
 50   123 
 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1 
 1   28 
 10   40 
 29   24 
 18   44 
 41   37 
 9   43 
 35   26 
 15   1 
 5   18 
 8   9 
 49   22 
 6   1 
 1   19 
 27   28 
 9   33 
 23   18 
 3   30 
 39   40 
 26   15 
 43   36 
 47   46 
 27   7 
 23   12 
 39   42 
 30   20 
 14   15 
 42   2 
 19   5 
 34   3 
 1   46 
 29   34 
 42   36 
 24   11 
 37   23 
 23   47 
 30   19 
 29   18 
 8   12 
 21   40 
 26   49 
 37   17 
 9   33 
 25   4 
 35   25 
 8   47 
 7   45 
 34   15 
 21   4 
 48   34 
 8   43 
 41   29 
 10   9 
 41   24 
 8   25 
 36   20 
 14   28 
 34   38 
 36   24 
 7   19 
 41   2 
 26   33 
 21   6 
 47   46 
 27   17 
 24   19 
 42   16 
 23   14 
 49   15 
 37   28 
 10   38 
 42   20 
 25   44 
 2   49 
 29   3 
 27   10 
 42   31 
 42   7 
 16   47 
 15   17 
 7   36 
 41   35 
 13   8 
 1   3 
 40   42 
 11   6 
 6   23 
 27   4 
 22   12 
 29   27 
 31   8 
 25   48 
 35   46 
 10   17 
 9   49 
 23   49 
 5   22 
 46   3 
 12   38 
 21   10 
 31   30 
 30   32 
 31   36 
 28   19 
 10   37 
 28   45 
 29   18 
 25   4 
 31   34 
 29   43 
 36   3 
 16   28 
 42   37 
 8   17 
 27   22 
 21   15 
 23   25 
 8   16 
 41   47 
 7   4 
 39   26 
 33   16 
 46   28 
 25   19

И вот такой выход у меня получается:
Код: plaintext
 13   16   9   1   4   21   24   24   20   27   22   2   24   15   15   14   1   2   5   1   29   3   21   23   20   16   28   7   29   8   25   1   15   17   21   23   21   1   29   28   30   28   9   1   1   12   13   18   15   1
...
Рейтинг: 0 / 0
17.10.2009, 21:23:49
| Ответить | Цитировать | Написать  
Задача на графы
    #36257480
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
Точно!
У меня ошибка на ошибке: этот граф-то с циклами и мой генератор теста кривой
...
Рейтинг: 0 / 0
17.10.2009, 22:16:19
| Ответить | Цитировать | Написать  
Задача на графы
    #36257484
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
junior idiot,
а как по скорости на 20000 вершинах? Можно без блока вывода.
По-прежнему совсем плохо? У меня пока нет под рукой хорошего графа.
...
Рейтинг: 0 / 0
17.10.2009, 22:19:35
| Ответить | Цитировать | Написать  
Задача на графы
    #36257499
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
junior idiotИ вот такой выход у меня получается:
Код: plaintext
 13   16   9   1   4   21   24   24   20   27   22   2   24   15   15   14   1   2   5   1   29   3   21   23   20   16   28   7   29   8   25   1   15   17   21   23   21   1   29   28   30   28   9   1   1   12   13   18   15   1

а у меня такой:...............
Код: plaintext
1.
 15   19   11   1   6   26   30   34   33   41   27   2   35   18   17   16   1   2   7   1   42   3   25   28   21   22   42   9   43   10   35   1   17   18   27   29   26   1   42   40   46   39   30   1   1   14   15   19   18   1
...
Рейтинг: 0 / 0
17.10.2009, 22:41:49
| Ответить | Цитировать | Написать  
Задача на графы
    #36257517
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
Ну вот, значит я еще и в реализации где-то напортачил пока пытался наоптимизировать.
А из тестов без циклов у меня есть только 2000 вершин и 22000 ребер, на них твой код отработал за 0.4 секунды из которых 0.3 ушло на вычисление ответов (на очень слабеньком нетбуке), что весьма круто, по-моему.
...
Рейтинг: 0 / 0
17.10.2009, 23:04:19
| Ответить | Цитировать | Написать  
Задача на графы
    #36257518
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
junior idiotНу вот, значит я еще и в реализации где-то напортачил пока пытался наоптимизировать.
А из тестов без циклов у меня есть только 2000 вершин и 22000 ребер, на них твой код отработал за 0.4 секунды из которых 0.3 ушло на вычисление ответов (на очень слабеньком нетбуке), что весьма круто, по-моему.
А вообще-то бред я написал, раз у меня ошибка, то и циклы в тесте есть, потому и отрабатывает быстро ("sch = 71")...
...
Рейтинг: 0 / 0
17.10.2009, 23:05:51
| Ответить | Цитировать | Написать  
Задача на графы
    #36257667
defrager
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
defrager
Гость
Вот правильная генерилка тестов гарантирующая отсутствие циклов.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
	cout <<  1  << endl;
	int N =  20000 ;
	int M =  500000 ;

	cout << N << " " << M << endl;

	for (int i =  0 ; i < N; i++)
	{
		printf("%d ", rand() %  1000 );
	}
	printf("\n");

	for (int i =  0 ; i < M; i++)
	{
		int first = (rand() % N);
		int second = first + (rand() % (N - first));

		printf("%d %d\n", first +  1 , second +  1 );
	}
...
Рейтинг: 0 / 0
18.10.2009, 09:42:46
| Ответить | Цитировать | Написать  
Задача на графы
    #36257689
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
defrager,

йес, это без циклов. Я даже навсякий проверил Питоном:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
import networkx as nx

a = open('E:\\C++\\SPOJ\\TestData\\4882in3.txt', 'rt').readlines()
a = a[ 3 :]
a = [tuple(map(int, ai.split())) for ai in a]

g = nx.DiGraph()
g.add_edges_from(a)

print nx.is_directed_acyclic_graph(g)


>>> 
True
>>>

Но теперь мой код в спойлере вообще не работает...
 
Код: 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.
#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, sch;
int w[nmx];
int t[nmx];
int b[nmx];
vector<int> p, q;
vector<int> d[nmx];
bitset<nmx> z[nmx];
bitset<nmx> c[nmx];


int main() {
    clock_t begin = clock();
    freopen("E:\\C++\\SPOJ\\TestData\\4882in3.txt", "rt", stdin);
    freopen("E:\\C++\\SPOJ\\TestData\\4882out.txt", "wt", stdout);
    tcs = read_ui();
    while (tcs-- > 0) {
        nv = read_ui();
        ne = read_ui();
        for (int i =  1 ; i <= nv; ++i) {
            w[i] = read_ui();
            t[i] =  0 ;
            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 (!c[u].test(v)) {
                ++b[u];
                c[u].set(v);
                d[v].push_back(u);
            }
        }

        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) {
                    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);
            sch += (int)p.size();
        }


        for (int i =  1 ; i <= nv; ++i)
            for (int k =  1 ; k <= nv; ++k) if (z[i].test(k))
                t[i] += w[k];
        for (int i =  1 ; i < nv; ++i) printf("%d ", t[i]);
        printf("%d\n", t[nv]);

        printf("sch = %d\n", sch);
        printf("Time = %.2f\n", (double)(clock() - begin) / CLOCKS_PER_SEC);
    }

return  0 ;
}



Выдает:
Код: plaintext
1.
2.
3.
 41   467   334   500  ... ... ...
sch =  0 
Time =  26 . 11

Счетчик sch = 0,
как будто в этом графе нет ни одной вершины без исходящего ребра и вектор "р" пустой
Я нихера не понимаю
...
Рейтинг: 0 / 0
18.10.2009, 11:05:47
| Ответить | Цитировать | Написать  
Задача на графы
    #36257762
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
> Я нихера не понимаю

Разгадка оказалась простой:
генерилка by defrager иногда генерит ребра вида (343 343)
Я вообще-то считал это за цикл. Но неважно, -- я вставил в код игнор таких глупых ребер.

И такие результаты для графа 20000/500000:
Код: plaintext
1.
2.
3.
4.
sch =  20000 
Time =  5 . 45 
 8467951   7916848   8095741   8352873   8309569  .......
Time =  33 . 42

В принципе неплохо, но для споджа надо в 2-3-4 раза быстрее.
Как и писал junior idiot почти всё время уходит на последний блок -- подсчета сумм.

 
Код: 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.
#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, sch;
int w[nmx];
int t[nmx];
int b[nmx];
vector<int> p, q;
vector<int> d[nmx];
bitset<nmx> z[nmx];
bitset<nmx> c[nmx];


int main() {
    clock_t begin = clock();
    freopen("E:\\C++\\SPOJ\\TestData\\4882in3.txt", "rt", stdin);
    freopen("E:\\C++\\SPOJ\\TestData\\99.txt", "wt", stdout);
    tcs = read_ui();
    while (tcs-- > 0) {
        nv = read_ui();
        ne = read_ui();
        for (int i =  1 ; i <= nv; ++i) {
            w[i] = read_ui();
            t[i] =  0 ;
            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);
            }
        }

        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) {
                    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);
            sch += (int)p.size();
        }

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

        for (int i =  1 ; i <= nv; ++i)
            for (int k =  1 ; k <= nv; ++k) if (z[i].test(k))
                t[i] += w[k];
        for (int i =  1 ; i < nv; ++i) printf("%d ", t[i]);
        printf("%d\n", t[nv]);

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

return  0 ;
}
...
Рейтинг: 0 / 0
18.10.2009, 12:52:13
| Ответить | Цитировать | Написать  
Задача на графы
    #36257889
defrager
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
defrager
Гость
Смотри пример в задаче - у них тоже есть такие ребра, поэтому лучше их не выбрасывать и тестировать с ними.

Что б получить accepted надо полностью менять алгоритм.
Если уж делать z[d[v][j]] |= z[v]; То надо быть полностью увереным что z[v] собрало всех своих чайлдов. Думай в сторону dfs
...
Рейтинг: 0 / 0
18.10.2009, 15:35:29
| Ответить | Цитировать | Написать  
Задача на графы
    #36257938
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
> поэтому лучше их не выбрасывать

Я их не выбрасываю (в моих тестах они как были так там и остаются) -- я их просто игнорю при чтении инпута

2.
Буду думать
...
Рейтинг: 0 / 0
18.10.2009, 16:33:40
| Ответить | Цитировать | Написать  
Задача на графы
    #36257953
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник

> Если уж делать z[d[v][j]] |= z[v];
> То надо быть полностью увереным что z[v] собрало всех своих чайлдов.
В том-то и засада, что у меня по построению z[v] именно уже собрало всех своих чилдренов.

На своей итерации вершина "v" накладывает свой окончательный битсет на битсеты всех своих
родителей и мы навсегда забываем про эту вершину.
Может это технически накладно, а алгоритмически вроде ничего.
...
Рейтинг: 0 / 0
18.10.2009, 16:50:45
| Ответить | Цитировать | Написать  
Задача на графы
    #36258299
defrager
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
defrager
Гость
Да алгоритм правильный, но его надо сильно оптимизировать а лучше переделать под dfs что б уложиться.

Подумай
1. Нужно ли нам запускать z[d[v][j]] |= z[v]; для каждого ребра исходящего (или входящего как у тебя) и когда можно не запускать. Эта операция не такая уж быстрая как кажется ~ O(20005 / 32)
2. Как лучше перебирать эти ребра что б этих "|=" было наименьшее число.
...
Рейтинг: 0 / 0
18.10.2009, 22:02:40
| Ответить | Цитировать | Написать  
Задача на графы
    #36258317
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
Если я правильно понимаю, само замыкание вроде довольно быстро строится (4-5 секунд), а основное время уходит уже на вычисление "ответа" ( О(N^2) - для 20000 весьма не кисло ). Разве нет?
...
Рейтинг: 0 / 0
18.10.2009, 22:14:20
| Ответить | Цитировать | Написать  
25 сообщений из 40, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача на графы
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=36238468&tid=1344166]:
 0ms
get settings:
 8ms
get forum list:
 8ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 233ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 37ms
get tp. blocked users:
 1ms
others: 189ms
total:  489ms
созд. / загр.: 489ms
x
x
Закрыть


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