Алгоритмы, методы, исходники / Форум

Алгоритмы, методы, исходники / Форум (http://forum.algolist.ru/)
-   Графы (http://forum.algolist.ru/algorithm-graph/)
-   -   Феи и конфетки (http://forum.algolist.ru/algorithm-graph/3748-fei-i-konfetki.html)

Livion 20.04.2010 21:57

Раскраска графа в два цвета
 
Помогите пожалуйста решить задачу, конечно лучше исходник, но идея тоже хорошо.
Текст задачи приложен

гость 21.04.2010 01:57

огласите источник задачи.

Livion 22.04.2010 21:13

Источник
 
Сссылка на источник
8D

lksh.ru


Задача в школе помогите решить все остальные решил, а тут даже идеи не придумать

гость 23.04.2010 00:37

Цитата:

Сообщение от Livion (Сообщение 11923)
Сссылка на источник
8D

http://tchikh.dyndns.org/9-01-08.pdf

то же мне источник, я тоже такой сварганить могу. ну да ладно.

Цитата:

Задача в школе помогите решить все остальные решил, а тут даже идеи не придумать
а че тут сложного я не пойму. прочел вашу задачу, там написано "раскрасьте граф в два цвета". задача для первоклашек. решается за линейное время любым видом обхода графа. вы какой предпочитаете в глубину, в ширину, рандомный? какой нравится такой и берите. алгоритм прост - берете любую вершину, и перебираете ее цвет (шоколадный или мармеладный). ваш выбор однозначно определяет цвета ее соседей, это в свою очередь - цвета их соседей и т.д. так как граф связан, вот вы и раскрасите его в процессе обхода. может случиться неприятная ситуации - нехватило конфет или у вершины есть и мармаладный и шоколадный сосед. тогда раскраски не существует. идем в начало и пробуем другой цвет для начальной вершины. в если уже все перебробовалы, тогда пишет нет.

гость 23.04.2010 20:48

Исходник
 
Можешь пожалуйста исходник написать

гость 24.04.2010 01:27

ну скажем вот примерно так на питоне:
Код:

#!/usr/bin/env python
# coding: utf-8
import sys

# чтение входа
N, M, S1, S2 = map(int, sys.stdin.readline().split())
adj = [[] for each in range(N + 1)]  # списки смежности

for each in range(M):
    a, b = map(int, sys.stdin.readline().split())
    adj[a].append(b)
    adj[b].append(a)

color = dict()  # color[x] будет равен цвету вершины

# процедура раскраски графа в два цвета, 0 и 1
def dfs(x, xcolor):
    color[x] = xcolor
    for y in adj[x]:
        if y not in color:  # если y не посетили
            dfs(y, 1 - xcolor)  # посещаем и назначаем противоположный цвет
        elif color[y] != 1 - xcolor:  # проверяем на совместимость
            raise 'граф раскрасить нельзя'

try:
    # назначаем вершине №1 цвет 0, и обходим граф начиная с нее
    dfs(x=1, xcolor=0)

    # считаем сколько какого цвета есть вершин
    num = [0, 0]
    for x in color.keys():
        num[color[x]] += 1

    # пробуем варианты 0=мармеладный 1=шоколадный и 0=шоколадный 1=мармеладный
    if (num[0] <= S1 and num[1] <= S2) or (num[0] <= S2 and num[1] <= S1):
        print 'YES'
        # TODO: вывод самой раскраски я оставляю как упражнение читателю
    else:
        print 'NO'
except:
    print 'NO'  # процедура dfs не смогла раскрасить граф

(на самом деле ровно так не заработает из за неглубокого стека. надо переписать на C, либо вместо рекурсивного обхода в глубину сделать итеративный)

гость 25.04.2010 00:09

Спасибо
 
Спасибо я щас на делфи перепешу

гость 25.04.2010 00:10

ап
 
жалко что на питоне(:

гость 25.04.2010 00:41

Исходник
 
А на делфи(лучше) можешь написать или на c++ , а то питона не понимаю


Часовой пояс GMT +4, время: 07:43.