Постановка задачи
Построить на n вершинах турнир, расстояние между любой парой вершин в котором не превышает двух рёбер.
Алгоритм решения
Условию удовлетворяет любая тройка вершин, принадлежащих циклу длины три, следовательно, искомый граф сильно связен. Уместно взять за основу полный неориентированный граф [latex]K_n[/latex] (не ограничивая общности рассуждений, будем представлять граф на плоскости как правильный [latex]n[/latex]-угольник) и задать на нём ориентацию рёбер согласно набору правил:
- Контур графа (рёбра вида [latex](k, k+1)[/latex]) ориентирован по часовой стрелке.
- В дальнейших построениях будем отталкиваться от контура: каждая вершина графа должна находиться в хотя бы в одном цикле длины три с данной. Опишем процедуру построения такого орграфа: начиная с вершины под номером 1 будем просматривать все остальные вершины. Если на некотором шаге ребро, связывающее вершины, не ориентировано, то ориентируем его образом, противоположным ориентации ребра, соединяющего текущую вершину-исток и предыдущую по номеру вершину в обходе. Более конструктивно процедура формулируется так: обойти все вершины в порядке их следования в контуре. Пусть номер стартовой вершины для исходной итерации — [latex]V_{i}[/latex], рассматриваемой на данном шаге — [latex]V_{k}[/latex] Если ребро [latex]\left(V_{i}, V_{k}\right)[/latex] не ориентировано, и номера обеих вершин (не)чётны — задать ориентацию [latex]\left[V_{i}, V_{k}\right][/latex], иначе — [latex]\left[V_{k}, V_{i}\right][/latex].
Исключение — граф [latex]K_4[/latex]: степень каждой вершины равна трём, следовательно, одно ребро каждой вершины не принадлежит контуру. Но таких рёбер всего два, следовательно, невозможно задать чередование ориентаций рёбер и получить четыре цикла длины 3. Для всех графов на большем числе вершин построение всегда возможно.
Реализация
ideone: http://ideone.com/XwY7fX
Засчитанное решение: http://codeforces.ru/contest/323/submission/10850799
Для решения задачи достаточно хранить граф в форме матрицы смежности.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <cstdio> unsigned G[1000][1000]; int main() { unsigned n; scanf("%u", &n); if(n == 4){ puts("-1"); } else{ for(size_t i = 0; i < n; i++){ G[i][(i+1)%n] = 1; } for(size_t i = 0; i < n; i++){ for(size_t j = 0; j < n; j++){ if(G[i][j] + G[j][i] == 0 && i != j){ if(i % 2 == j % 2) G[i][j] = 1; else G[j][i] = 1; } } } for(size_t i = 0; i < n; i++){ for(size_t j = 0; j < n-1; j++){ printf("%u ", G[i][j]); } printf("%u\n", G[i][n-1]); } } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
import java.util.*; import java.io.*; import java.math.*; class Solver { public static void main(String args[]) throws IOException{ new Solver().run(); } StreamTokenizer in; PrintWriter out; int nextInt() throws IOException{ in.nextToken(); return (int)in.nval; } void run() throws IOException{ in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); out = new PrintWriter(new OutputStreamWriter(System.out)); solve(); out.flush(); } void solve() throws IOException{ int n = nextInt(); int[][] G = new int[n][n]; if(n == 4) out.println("-1"); else{ for(int i = 0; i < n; i++) G[i][(i+1)%n] = 1; for(int y = 0; y < n; y++){ for(int x = 0; x < n; x++){ if(G[y][x] + G[x][y] == 0 && x != y){ if(y % 2 == x % 2) G[y][x] = 1; else G[x][y] = 1; } } } for(int y = 0; y < n; y++){ for(int x = 0; x < n-1; x++){ out.print(G[y][x]); out.print(" "); } out.println(G[y][n-1]); } } } } |
Принято на 98,3%. Тест №51 на e-olimp не заходит.
CodeForces заслуживает доверия: и компилятор там новее, и набор тестов аналогичен вплоть до количества (и, наверняка, порядка следования). К сожалению, я так и не смог придумать способа обойти «Ошибку проверки», причем, с проверяющей системой e-olimp подобные ситуации случаются систематично.
Java решение засчитано, 10 баллов.