Задача №541. Столица (informatics)

В некотором царстве, в некотором государстве было N городов, и все они, судя по главной карте императора, имели целые координаты. В те годы леса были дремучие, дороги же строить умели только параллельно осям координат, так что расстояние между двумя городами определялось как |x1 - x2| + |y1 - y2|.
Император решил построить N+1-ый город и сделать его столицей своего государства, при этом координаты столицы также должны быть целыми. Место для столицы следует выбрать так, чтобы среднее арифметическое расстояний между столицей и остальными городами было как можно меньше. Однако, разумеется, столицу нельзя строить на месте существующего города.
Нелегкая задача выбрать место для столицы поручена Вам.

Входные данные
В первой строке вводится число N - количество городов (1 <= N <= 100). Следующие N строк содержат координаты городов - пары целых чисел, не превышающих 1000 по абсолютной величине.

Выходные данные
Выведите два целых числа - координаты точки, где следует построить столицу. Если решений несколько, выведите любое.

входные данные
8
0 0
1 0
2 0
0 1
2 1
0 2
1 2
2 2

выходные данные
1 1

входные данные
4
0 0
1 1
0 1
1 0

выходные данные
0 -1

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define pb push_back
#define int long long
#define F first
#define S second
using namespace std;
const int N = 1000;
int x[N], y[N];
int r[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int32_t main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	int n;
	cin >> n;
	set <pair <int, int>> st;
	for (int i = 0; i < n; ++i) {
    	int a, b;
    	cin >> a >> b;
    	st.insert({a, b});
    	x[i] = a;
    	y[i] = b;
	}
	sort(x, x + n);
	sort(y, y + n);
	int xx = x[n / 2], yy = y[n / 2], ans = 2e15 + 7; // нахождение центральной манхеттанской точки
	if (st.count({xx, yy}) > 0) { // если центральная точка занята
    	for (auto to : st){
        	for (int k = 0; k < 4; ++k) { // проверка 4 соседей каждого заданного города
            	int x1 = to.F + r[k][0], y1 = to.S + r[k][1];
            	int dist = 0;
            	if (st.count({x1, y1}) > 0) continue;
            	for (auto now : st) { // нахождение суммы минимальных расстояний до всех городов от (x1, y1)
                	int x2 = now.F, y2 = now.S;
                	dist += abs(x1 - x2) + abs(y1 - y2);
            	}
            	if (dist < ans) { // выбор лучшей суммы
                	ans = dist;
                	xx = x1; yy = y1;
            	}
        	}
    	}
	}
	cout << xx << ' ' << yy;
	return 0;
}

Автор статьи: Андреева Даша

Поиск в глубину (англ. depth-first search, DFS) – это рекурсивный алгоритм обхода вершин графа. Если метод поиска в ширину производился симметрично (вершины графа просматривались по уровням), то данный метод предполагает продвижение вглубь до тех пор, пока это возможно. Невозможность дальнейшего продвижения, означает, что следующим шагом будет переход на последнюю, имеющую несколько вариантов движения (один из которых исследован полностью), ранее посещенная вершина.

Пошаговое представление

1. Выбираем любую вершину из еще не пройденных, обозначим ее как v

2. Запускаем процедуру dfs(v)

• Помечаем вершину v как пройденную
  
• Для каждой не пройденной смежной с v вершиной (назовем ее to) запускаем dfs(to)

3. Повторяем шаги 1 и 2, пока все вершины не окажутся пройденными

Алгоритм работает за O (N+M)

Применение алгоритма

• Поиск любого пути в графе
  
• Есть ли путь из вершины S в вершину F
  
• Связный ли граф
  
• Сколько компонент связности
  
• Поиск лексикографически первого пути в графе
  
• Топологическая сортировка:
  Запускаем серию поисков в глубину, чтобы обойти все вершины графа. Отсортируем вершины по времени выхода по убыванию - это и будет ответом.
  
• Задача LCA (наименьший общий предок)

Реализация
Рассмотрим задачу:
В стране Z есть N городов, которые соединены M дорогами. По дорогам можно ездить в обоих направлениях. Между двумя городами могут существовать несколько дорог, также дорога может вести из города в его же самого. Правительство страны хочет определить количество изолированных друг от друга областей в стране. Область – это набор городов, где между любой парой городов есть путь. Помогите правительству определить это количество.
Формат ввода:
N, M – количество городов и дорог.
Далее следует M строк с описанием дорог. Каждая дорога описывается парой чисел – города которые она соединяет.
Решение:
Решение задачи сводится к нахождению количества компонент связности в графе.

int32_t main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
    	int x, y;
    	cin >> x >> y; x--; y--;
    	if (x == y) continue;
    	g[x].insert(y);
    	g[y].insert(x);
	}
	int k = 0;
	for (int i = 0; i < n; ++i) p[i] = 0;
	for (int i = 0; i < n; ++i) {
    	if (!p[i]){
        	dfs(i);
        	k++;
    	}
	}
	cout << k << endl;
	return 0;
}

• Прочитаем список смежности графа
  
• Пометим все вершины как не пройденные
  
• Пройдем по всем вершинам

Если вершина не пройдена

• Запустим dfs от этой вершины
  
• Увеличим ответ

• Выведем ответ

Сам dfs:

set < int > g[N];
bool p[N];
void dfs (int v){
	if (!p[v]){
    	p[v] = 1;
    	for (auto to:g[v]){
        	if (!p[to]) dfs(to);
    	}
	}
}

Сдать задачу:http://dl.gsu.by/tas...=1062969&cid=19
Если ссылка не открывается:
dl.gsu.by Олимпиады по информатике Гомельская гор. 13.10.2012 изолированные города