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

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

Войти
Регистрация
Восстановить пароль
 
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
#1

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

08.03.2014, 19:40. Просмотров 543. Ответов 0
Метки нет (Все метки)

Есть задача: [перепечатайте в пост]

Может кто-то мне объяснить як ее сделать. Вот ссылка на решение автора:
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++
В метании молота состязается n спортcменов. Каждый из них сделал m бросков. Побеждает спортсмен, у которого максимален наилучший бросок....

Codeforces.Double Cola - C++
Условие задачи таково: Шелдон, Леонард, Пенни, Раджеш и Говард стоят в очереди к автомату по продаже баночек с напитком «Double Cola»,...

Разбор задания - C++
Добрый вечер уважаемые эксперты! Есть следующее задание: составить двусвязный список объектов класса описывающего студента (Ф.И.О. номер...

Разбор ошибок - C++
Задача - Для целочисленной квадратной матрицы найти число элементов , кратных К и наибольший элемент из найденных кратных числу К...

Разбор строки - C++
Здравствуйте. В stdin программы приходит строка вида domain=d.ru&amp;type=delete&amp;file=std&amp;... При этом мне необходимо получить значение...

разбор ошибок - C++
всем доброго времени суток! написал прогу которая работаес с базой данных. в студии все прекрасно работало, но нада на Борланд С++ 3.1 ....

Разбор кода - C++
Помогите, пожалуйста, разобрать данный код. Многое из этого мне еще не знакомо. Поэтому не могу уловить суть действий. Чем больше будет...

Разбор алгоритма - C++
Пожалуйста поясните метод сжатия LZMA. Только пожалуйста не надо кидать ссылки на википедию.

Разбор XML - C++
Начинаю разбираться с прочтением XML нашёл пример и он не хочет работать жалуется компилятор на функции xmlParseFile, xmlDocGetRootElement,...

разбор программы - C++
Друг написал прогу, но комментарии к ней не сделал, поэтому не понятно. Помогите разобраться с программой. Вот условие: Создать класс...


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

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

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