Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 20.04.2010, 21:57
Новичок

Отправить личное сообщение для Livion Посмотреть профиль Найти все сообщения от Livion
 
Регистрация: 20.04.2010
Сообщений: 4

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

Последний раз редактировалось Livion, 25.04.2010 в 15:30. Причина: Заголовок
  #2  
Старый 21.04.2010, 01:57
гость

 
Сообщений: n/a

огласите источник задачи.
  #3  
Старый 22.04.2010, 21:13
Новичок

Отправить личное сообщение для Livion Посмотреть профиль Найти все сообщения от Livion
 
Регистрация: 20.04.2010
Сообщений: 4

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

lksh.ru


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

Последний раз редактировалось Livion, 25.04.2010 в 15:28.
  #4  
Старый 23.04.2010, 00:37
гость

 
Сообщений: n/a

Сообщение от Livion Посмотреть сообщение
Сссылка на источник
8D

http://tchikh.dyndns.org/9-01-08.pdf
то же мне источник, я тоже такой сварганить могу. ну да ладно.

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

 
Сообщений: n/a

Исходник
Можешь пожалуйста исходник написать
  #6  
Старый 24.04.2010, 01:27
гость

 
Сообщений: n/a

ну скажем вот примерно так на питоне:
Код:
#!/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, либо вместо рекурсивного обхода в глубину сделать итеративный)
  #7  
Старый 25.04.2010, 00:09
гость

 
Сообщений: n/a

Спасибо
Спасибо я щас на делфи перепешу
  #8  
Старый 25.04.2010, 00:10
гость

 
Сообщений: n/a

ап
жалко что на питоне(:
  #9  
Старый 25.04.2010, 00:41
гость

 
Сообщений: n/a

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра