Skip to Content
CTRL K

Redistributing Gifts

Análisis oficial (C++) 

Solución 1

Ver el análisis oficial.

Solución 2 - Componentes fuertemente conexas

Explicación

De forma similar al análisis oficial, podemos construir una arista dirigida de ii a jj si la vaca ii prefiere el regalo jj al regalo ii. Si la vaca ii puede recibir un regalo hacia el que tiene una arista saliente, entonces la vaca ii ha recibido el regalo más óptimo que se le puede reasignar. Recordemos también añadir una arista de la vaca ii a sí misma por si no puede obtener un regalo mejor.

Luego, podemos separar el grafo en componentes fuertemente conexas (SCC). Si ii está en una SCC, esto significa que la vaca ii puede recibir todos los regalos de la SCC mediante una serie de reasignaciones, por definición de SCC. La SCC también debe tener al menos uno de los regalos preferidos de la vaca ii porque debe contener al menos una arista saliente de ii. Si una vaca no pertenece a una SCC, no puede recibir una reasignación más óptima.

Implementación

El algoritmo de Kosaraju  se puede usar para hallar todas las SCC del grafo. Al final, es óptimo simplemente bajar por la lista de preferencias de la vaca ii y asignar el primer regalo que pertenezca a la SCC.

Complejidad temporal: O(N2)\mathcal{O}(N^2)

#include <bits/stdc++.h>
 
using namespace std;
const int N = 501;
 
// Las listas de adyacencia del grafo (revgraph está invertido)
vector<int> graph[N], revgraph[N];
vector<bool> vis(N), vis2(N);
vector<int> path;
 
// comp[i] = true si i está en el componente
vector<bool> comp(N);
 
// Funciones DFS para el algoritmo de Kosaraju
void dfs(int node) {
	vis[node] = true;
	for (int i : graph[node]) {
		if (!vis[i]) { dfs(i); }
	}
	path.push_back(node);
}
 
void dfs2(int node, vector<int> &comp_nodes) {
	vis2[node] = true;
	for (int i : revgraph[node]) {
		if (!vis2[i]) { dfs2(i, comp_nodes); }
	}
	comp[node] = true;
	comp_nodes.push_back(node);
}
 
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		// El arreglo graph contiene los regalos preferidos de la vaca i (y ella misma).
		graph[i].resize(n);
		for (int j = 0; j < n; j++) { cin >> graph[i][j]; }
		/*
		 * No queremos aristas a regalos no preferidos,
		 * así que quitamos todos los regalos posteriores a su asignación original.
		 */
		while (graph[i].back() != i) { graph[i].pop_back(); }
		for (int j : graph[i]) { revgraph[j].push_back(i); }
	}
 
	// implementación clásica de Kosaraju
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) { dfs(i); }
	}
 
	reverse(path.begin(), path.end());
 
	vector<int> ans(n + 1);
	for (int i : path) {
		if (!vis2[i]) {
			vector<int> comp_nodes;
			dfs2(i, comp_nodes);
			/*
			 * Recorrer todas las vacas de la SCC y su lista de preferencias.
			 * Si se encuentra un regalo en su preferencia y también en la SCC,
			 * se lo asignamos a la vaca.
			 */
			for (int j : comp_nodes) {
				for (int k : graph[j]) {
					if (comp[k]) {
						ans[j] = k;
						break;
					}
				}
			}
			for (int j : comp_nodes) { comp[j] = false; }
		}
	}
 
	for (int i = 1; i <= n; i++) { cout << ans[i] << endl; }
}
Fundamentos