1 Тема від sublemate Востаннє редагувалося sublemate (13.05.2015 20:21:10)

  • sublemate
  • Користувач
  • Поза форумом
  • Дата реєстрації: 13.05.2015
  • Повідомлень: 2
    • Репутація: 0

Тема: Задача з e-olimp. Теорія графів. Водопровід.

Допоможіть з задачою , взагалі не розумію, а потрібно написати код ...

Місто складається з N районів (1  N  100).

Кожен район має свердловину для отримання води. Кожні дві свердловини з’єднані між собою трубою. По кожній трубі вода може текти тільки в одному напрямку. Внаслідок енергетичної кризи в кожен момент часу працює тільки одна свердловина.  Оскільки система проектувалася без передбачення такого режиму роботи, деякі райони міста інколи залишаються без води.

Завдання. Напишіть програму WATER.*, яка визначить чи можна, змінивши напрямок проходження води по трубах, що приєднані до однієї із свердловин, добитись безперервного водопостачання в місті.

Вхідні дані. В першому рядку файлу WATER.DAT знаходиться число N – кількість районів (свердловин) в місті. В наступних N рядках для кожної свердловини вказуються кількість та номери свердловин, з яких до неї надходить вода. Свердловини мають номери від 1 до N.

Вихідні дані. В єдиному рядку файлу WATER.SOL має бути одне число – номер шуканої свердловини, якщо така існує, або 0 в іншому випадку.

Вхіні дані:
4
0
1 1
2 1 2
3 1 2 3
Вихідні дані:
1

Post's attachments

1.png 2.11 kb, 200 downloads since 2015-05-13 

2 Відповідь від Joker

  • Joker
  • Користувач
  • Поза форумом
  • Дата реєстрації: 27.04.2014
  • Повідомлень: 953
    • Репутація: 121

Re: Задача з e-olimp. Теорія графів. Водопровід.

▼Якщо ви намагалися її вирішити, але у вас нічого не получилося
#include <iostream>
using namespace std;

bool g[101][101];
bool used[101];
int n;

void dfs(int b)
{
    used[b] = 1;

    for (int i = 1; i <= n; ++i)
    {
        if (g[i][b] && !used[i])
            dfs(i);
    }

}

int main()
{

    cin >> n;
    int z, x;

    for (int i = 1; i <= n; ++i)
    {
        cin >> z;
        for (int j = 0; j < z; ++j)
        {
            cin >> x;
            g[i][x] = 1;
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
            swap(g[i][j], g[j][i]);

        for (int q = 1; q <= n; ++q)
        {
            memset(used, 0, n);
            dfs(q);
            for (int i = 1; i <= n; ++i)
            {
                if (!used[i])
                    goto ADD;
            }

        }

        cout << 1 << endl;
        return 0;
    ADD:
        for (int j = 1; j <= n; ++j)
            swap(g[i][j], g[j][i]);

    }
    cout << 0 << endl;
    return 0;
}

Розкажіть про хід ваших думок при виконанні цієї задачі, будь ласка.