Семинар 24.02 Подгруппа 106-2
Домашнее задание: Задач на допуск к контесту на этой неделе нет. Есть просто задачка. Дан неориентированный граф. На ребрах графа записаны целые веса w_i. Нужно для данного графа расставить на вершинах целые веса, так что сумма весов на двух вершинах, соединенных ребром, будет равна весу ребра по модулю N, где N - некоторое целое число, которое тоже дается на вход функции.
Если такое невозможно, функция должна об этом сообщить, например, вернуть false.
Вершину в задаче можно представить, например, так:
struct Edge { int weight; int to // node index }; struct Node { vector<Edge> edges; };
Тогда функция будет иметь такой вид:
bool TryFindNodeWeights(const vector<Node>& graph, vector<int>* result) { // result[i] == weight of i-th node. // return true if success else false. }
Также нужно написать набор ручных тестов: графы, на котором получилось проставить веса: граф без циклов, граф с четным циклом, граф с нечетным циклом, а также граф на котором не получилось проставить веса.