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

Разбор задачи с Codeforces - C++

Восстановить пароль Регистрация
 
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
08.03.2014, 19:40     Разбор задачи с Codeforces #1
Есть задача: [перепечатайте в пост]

Может кто-то мне объяснить як ее сделать. Вот ссылка на решение автора:
http://codeforces.ru/blog/entry/10755

Также есть чужое решение (помогите его разобрать):

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
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <limits>
#include <tuple>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
 
using namespace std;
 
const int C=1e6;
int n, m, k, ty[C], c[555], d[555][555], u[C], uc[555], lo[555], ls;
vector<int> t[C];
void go(int v)
{
    if (!uc[ty[v]]) lo[ls++]=ty[v];
    ++uc[ty[v]];
    u[v]=1;
    for (int i=0;i<t[v].size();++i) if (!u[t[v][i]]) go(t[v][i]);
}
void sm(int &a, int x)
{
    if (a==-1||a>x) a=x;
}
int main()
{
    scanf("%d %d %d", &n, &m, &k);
    for (int i=0;i<k;++i) scanf("%d", &c[i]);
    for (int i=0, s=0;i<k; s+=c[i], ++i) {
        for (int j=s; j<s+c[i]; ++j) {
            ty[j]=i;
        }
    }
    for (int i=0;i<k;++i) for (int j=0;j<k;++j) if (i!=j) d[i][j]=-1;
    for (int i=0;i<m;++i)
    {
        int a, b, x;
        scanf("%d %d %d", &a, &b, &x);
        --a; --b;
        if (x==0)
        {
            t[a].push_back(b);
            t[b].push_back(a);
        }
        a=ty[a];
        b=ty[b];
        sm(d[a][b], x);
        sm(d[b][a], x);
    }
    for (int i=0;i<n;++i)
    {
        if (uc[ty[i]]) continue;
        int pp=ls;
        go(i);
        for (int j=pp;j<ls;++j) if (uc[lo[j]]!=c[lo[j]]) { puts("No"); return 0; }
    }
    for (int l=0;l<k;++l) for (int i=0;i<k;++i) for (int j=0;j<k;++j)
    {
        if (d[i][l]!=-1&&d[l][j]!=-1) sm(d[i][j], d[i][l]+d[l][j]);
    }
    puts("Yes");
    for (int i=0;i<k;++i) for (int j=0;j<k;++j) printf("%d%c", d[i][j], j+1==k?'\n':' ');
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.03.2014, 19:40     Разбор задачи с Codeforces
Посмотрите здесь:

C++ Разбор задания
Разбор кода C++
разбор программы C++
C++ Разбор OpenSource
C++ Разбор XML
C++ Codeforces.Double Cola
Разбор задачи на построение массивов C++
Разбор задачи на конструкторы C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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