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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 07.12.2009, 03:56
topless

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

Поиск в ширину. Двудольный граф
Есть такая задача:
«Разбиение на группы не знакомых»

Условие:
Имеется N человек и матрица А размера N?N. Элемент A[i,j] матрицы равен 1, если человек i знаком с человеком j (если i-ый человек знает j-ого, то считаем, что и j-ый человек знает i-ого) и элемент A[i,j] матрицы равен 0, если i-ый человек не знаком с человеком j. Можно ли разбить людей на 2 группы, чтобы в каждой группе были только незнакомые люди.

Входные данные
Входные данные находятся в файле input.in.

Первая срока содержит количество людей N.
Затем идут N строк файла, которые задают матрицу знакомств A (каждой строке матрицы соответствует отдельная строка входного файла, числа в строках разделены пробелами).

Выходные данные
Выходные данные находятся в файле output.out.

Если можно разбить людей на две группы, чтобы в каждой группе были только незнакомые люди, то первая строка файла содержит сообщение “YES”, а вторая строка содержит номера людей, которые попали в одну из групп. Числа в строке разделяются одним пробелом и упорядочены по возрастанию. Если нет, то единственная строка файла содержит сообщение “NO”.

Пример входных данных
4
0 1 0 1
1 0 1 1
0 1 0 1
1 1 1 0

Пример выходных данных
NO

или

Пример входных данных
10
0 1 0 0 1 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 1 0 1
0 0 1 0 0 1 0 0 1 0
1 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1 0 1
0 0 1 0 0 0 0 0 1 0
0 0 1 0 0 1 0 0 1 0
0 0 0 1 0 0 1 1 0 0
0 0 1 0 0 1 0 0 0 0

Пример выходных данных
YES
1 3 6 9

это надо до этого вторника сделать. бля, тока вот спать ложился и вспонимл... дурень, сроки перепутал...выручите меня кто шарит. надо на С++

задача сводится к определению того, двудольный граф это, или нет (например, определяете это поиском в ширину). Если двудольный граф, то ответ "да". и немного попотеть.

пример входных данных должен находиться в вышеименнованом файле.
вот, что успел накидать каркас:

#include "stdafx.h"

#include <fstream>
#include <iostream>
using namespace std;

int main(){
int row,col;
ifstream InFile("input.in");
if (!InFile){
cout << endl << "Error !";
}
InFile >> row; // считываем размер массива

const long n=10;
long int A[n][n];

for(int i = 0; i < row; i++){
for (int j = 0; j < row; j++){
InFile >> A[i][j];
}
}
InFile.close();

for (int i = 0; i < row; i++){
for (int j = 0; j < row; j++){
cout << A[i][j] << "\t";
}
cout << "\n";
}

//================================
//тут алгоритм или еще что))
//================================

ofstream OutFile("output.out");
if(!OutFile){
cout << "Ошибка в файле!\n";
}
OutFile << "NO";
OutFile.close();

return 0;
}
  #2  
Старый 07.12.2009, 04:13
гость

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

Кстати, необязательно поиск в ширину использовать. Любой абсолютно алгоритм обхода графа тут подойдет, поиск в глубину, даже дейкстра, и т.п.
  #3  
Старый 07.12.2009, 04:15
topless

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

я уже это понял, полазив по википедии и по каким-то лекциям с Питерского ВУЗа)тока глаза уже вырубаются напрочь
  #4  
Старый 07.12.2009, 13:51
гость

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

Стандартная задача на графы. Дан граф - проверить является ли он двудольным. Граф двудольный тогда и только тогда когда все циклы четны. Решается за один обход в глубину. На каждом шаге обхода в глубину метим вершину. Допустим мы пошли в первую вершину - добавляем ее в первую группу. То есть ставим метку один. Затем просматриваем все смежные вершины и если не помечена вершина, то метим ее как 2(то есть запихиваем в противоположную группу) и и рекурсивно переходим в нее. Если же она мечена и у нее такая же метка как у нашей - то все граф не двудольный.
  #5  
Старый 27.02.2011, 22:34
гость11

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

Сообщение от гость Посмотреть сообщение
Стандартная задача на графы. Дан граф - проверить является ли он двудольным. Граф двудольный тогда и только тогда когда все циклы четны. Решается за один обход в глубину. На каждом шаге обхода в глубину метим вершину. Допустим мы пошли в первую вершину - добавляем ее в первую группу. То есть ставим метку один. Затем просматриваем все смежные вершины и если не помечена вершина, то метим ее как 2(то есть запихиваем в противоположную группу) и и рекурсивно переходим в нее. Если же она мечена и у нее такая же метка как у нашей - то все граф не двудольный.
большое вам спасибо!
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Обход дерева в ширину. Delphi 7. гость Реализация, исходники, языки 9 23.06.2009 08:54
граф в win32 гость Графы 11 08.04.2009 03:07
поиск в ширину IgNik500 Реализация, исходники, языки 5 02.12.2008 17:54
задача про кубический граф гость Графы 4 22.05.2008 09:42
поиск в ширину emc2 Графы 1 01.05.2008 07:00