2020 - Graph

Solución en video

Por David Zhou

Nota: la solución en video puede no coincidir con las demás. Código en C++ y Java.

Solución

Explicación

Propagación de restricciones

Supongamos que el valor de un extremo de una arista es $u$ . Si $u + v = s$ , entonces podemos hallar el valor del otro extremo como $v = s - u$ . Con base en esto, si fijamos el valor de un nodo en una componente conexa, todos los demás valores de esa componente quedan determinados siguiendo las aristas.

Determinar los valores generales de los nodos

Para cada componente conexa, podemos expresar todos los valores de los nodos en términos de una sola variable $x$ :

Empezamos con un nodo arbitrario y le asignamos el valor $x$
Luego propagamos por las aristas. Si $u = ax + b$ y la arista $(u,v)$ tiene suma $s$ , entonces $v = s - u = -ax + (s - b)$

Esto significa que el valor de cada nodo se representa de la forma $cx + d$ , donde $c=\pm1$ .

Comprobar factibilidad en componentes conexas cíclicas

Encontramos un ciclo cuando visitamos un nodo ya visitado. Esto significa que hay que comprobar factibilidad.

Si volvemos a llegar al nodo $u$ , tenemos dos expresiones para él
El ciclo nos da una ecuación en términos de $x$
Si la ecuación no tiene solución o contradice una solución previa, el problema es infactible

Por qué las ecuaciones de ciclo determinan x

Consideremos un camino del nodo $u$ de vuelta a sí mismo. Sea $u = a_1x + b_1$ nuestro valor inicial para la propagación. Más adelante, si volvemos en un bucle, obtendremos otra expresión $u = a_2x + b_2$ .

Caso 1: $a_1 = a_2$ : Obtenemos $b_1 = b_2$ . Si $b_1 \neq b_2$ , la componente conexa es infactible, así que el grafo entero es infactible.

Caso 2: $a_1 \neq a_2$ : Podemos resolver: $x = \dfrac{b_2-b_1}{a_1 - a_2}$ , lo que determina de forma única un valor para $x$ .

Componentes conexas acíclicas

Cuando ningún ciclo determina $x$ , hay que elegir su valor para minimizar la expresión: $\sum_{i=1}^n |a_i x + b_i|$ . Esto se puede hacer poniendo $x$ como la mediana de las raíces, porque este problema se reduce a minimizar la suma de diferencias absolutas.

Por qué la mediana minimiza la suma

Queremos minimizar la función $f(x) = \sum_{i=1}^n |a_i x + b_i|$ .

Como cada $a_i \in \{+1, -1\}$ , podemos reescribir cada término como $|a_i x + b_i| = |x - r_i|$ , donde $r_i = -\dfrac{b_i}{a_i}$

Así, minimizar $f(x)$ es equivalente a minimizar $f(x) = \sum_{i=1}^n |x - r_i|$

De forma intuitiva, podemos pensar en intentar empujar $x$ lo más cerca posible del medio de las raíces, porque colocarlo ahí “equilibra” los valores.

Matemáticamente, podemos fijar cualquier $x \in \mathbb{R}$ y un incremento positivo pequeño $h > 0$ de modo que ninguna $r_i$ quede en el intervalo $(x, x + h]$ .

Consideremos el cambio $f(x + h) - f(x) = \sum_{i=1}^{k} (|x + h - r_i| - |x - r_i|)$ .

Para cada $i$ , ocurre una de dos cosas:

Si $r_i \le x$ , entonces $|x + h - r_i| - |x - r_i| = h$ .
Si $r_i > x$ , entonces $|x + h - r_i| - |x - r_i| = -h$ .

Por lo tanto, $f(x + h) - f(x) = h \cdot(\# {\{i : r_i \le x\}} - \# {\{i : r_i > x\}})$ .

Sean $L(x) = \# {\{i : r_i \le x\}}$ y $R(x) = \# {\{i : r_i > x\}}$ . Nótese que $L(x) + R(x) = n$ .

Si $L(x) < R(x)$ entonces $f(x + h) - f(x) < 0$ , así que moverse un poco a la derecha disminuye $g$ .

Si $L(x) > R(x)$ entonces $f(x + h) - f(x) > 0$ , así que moverse un poco a la derecha aumenta $g$ . De forma equivalente, moverse a la izquierda disminuye $g$ .

Si $L(x) = R(x)$ entonces $f(x + h) = f(x)$ . Los movimientos no afectan el valor de $g$ .

Por lo tanto, los únicos mínimos posibles ocurren en puntos donde $L(x) \ge R(x)$ y $R(x) \ge L(x)$ . Esto significa o bien $L(x) = R(x)$ o que moverse en cualquiera de las dos direcciones deja los conteos equilibrados. Esto es cierto en la mediana de las raíces.

Determinar los valores reales de los nodos

Independientemente de cómo hayamos computado $x$ , una vez que lo tenemos, hay que propagar este valor por las componentes conexas. Podemos sustituir $x$ en cada $ax + b$ y determinar el valor exacto de cada nodo que minimiza la suma de sus valores absolutos.

Implementación

Complejidad temporal: $\mathcal{O}(N\log N + M)$

C++Java


#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>
 
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
 
const ll INF = 1e18;
 
vector<vector<pll>> adj;
vector<pll> coeffs;  // el valor de cada nodo se representa como ax + b (guardado como par {a, b})
vector<bool> vis;
vector<double> ans;
vector<int> current_component;
bool impossible;
ll current_val;
 
void dfs(int u) {
	current_component.push_back(u);
	vis[u] = true;
 
	for (auto [v, w] : adj[u]) {
		if (vis[v]) {
			// hallamos un ciclo -> comprobamos consistencia o resolvemos para x
			pll res = {coeffs[u].first + coeffs[v].first,
			           coeffs[u].second + coeffs[v].second};
 
			if (res.first == 0) {
				// los términos en x se cancelan -> comprobamos si las constantes coinciden
				if (res.second != w) { impossible = true; }
			} else {
				// podemos resolver para x
				ll expected;
				if (res.first == 2) {
					expected = w - res.second;
				} else {
					expected = res.second - w;
				}
				if (current_val == INF) {
					current_val = expected;
				} else if (current_val != expected) {
					// contradicción con el x determinado previamente
					impossible = true;
					return;
				}
			}
		} else {
			// computamos el valor del vecino según la arista: v = w - u
			coeffs[v] = {-coeffs[u].first, w - coeffs[u].second};
			dfs(v);
		}
	}
}
 
void propagate(int u) {
	// una vez conocido x, propagamos los valores reales por la componente
	vis[u] = true;
	for (auto [v, w] : adj[u]) {
		if (!vis[v]) {
			ans[v] = w - ans[u];
			propagate(v);
		}
	}
}
 
double find_median(const vector<int> &comp) {
	// el x óptimo minimiza la suma de |ax+b|, que ocurre en la mediana de las raíces
	vector<ll> roots;
	for (int node : comp) {
		if (coeffs[node].first == 1) {
			roots.push_back(-coeffs[node].second);
		} else {
			roots.push_back(coeffs[node].second);
		}
	}
	sort(roots.begin(), roots.end());
	int sz = roots.size();
	return (roots[(sz - 1) / 2] + roots[sz / 2]) / 2.0;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int n, m;
	cin >> n >> m;
 
	adj.resize(n);
	coeffs.assign(n, {-INF, -INF});
	vis.assign(n, false);
	ans.resize(n);
	impossible = false;
 
	// construimos la lista de adyacencia
	for (int i = 0; i < m; i++) {
		int a, b;
		ll c;
		cin >> a >> b >> c;
		--a, --b;
		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
	}
 
	vector<vector<int>> components;
	vector<ll> component_vals;
 
	// hallamos todas las componentes conexas
	for (int i = 0; i < n; i++) {
		if (!vis[i]) {
			current_component.clear();
			current_val = INF;
			coeffs[i] = {1, 0};  // el primer nodo = x
			dfs(i);
			components.push_back(current_component);
			component_vals.push_back(current_val);
		}
	}
 
	if (impossible) {
		cout << "NO\n";
		return 0;
	}
 
	cout << "YES\n";
	fill(vis.begin(), vis.end(), false);
 
	// computamos los valores finales de cada componente
	for (int i = 0; i < components.size(); i++) {
		int start = components[i][0];
		if (component_vals[i] == INF) {
			// x no está fijo -> usamos la mediana para la suma óptima
			ans[start] = find_median(components[i]);
		} else {
			// x quedó determinado por un ciclo
			ans[start] = component_vals[i] / 2.0;
		}
		propagate(start);
	}
 
	for (int i = 0; i < n; i++) {
		cout << fixed << setprecision(1) << ans[i];
		if (i == n - 1) {
			cout << '\n';
		} else {
			cout << ' ';
		}
	}
}


import java.io.*;
import java.util.*;
 
public class Graph {
	static final long INF = (long)1e18;
 
	static List<List<Pair>> adj;
	static List<Pair> coeffs;  // valor del nodo representado como ax + b (guardado como {a, b})
	static boolean[] vis;
	static double[] ans;
	static List<Integer> currentComponent;
	static boolean impossible;
	static long currentVal;
 
	static class Pair {
		long first, second;
		Pair(long first, long second) {
			this.first = first;
			this.second = second;
		}
	}
 
	static void dfs(int u) {
		currentComponent.add(u);
		vis[u] = true;
 
		for (Pair edge : adj.get(u)) {
			int v = (int)edge.first;
			long w = edge.second;
 
			if (vis[v]) {
				// hallamos un ciclo -> comprobamos consistencia o resolvemos para x
				Pair res = new Pair(coeffs.get(u).first + coeffs.get(v).first,
				                    coeffs.get(u).second + coeffs.get(v).second);
 
				if (res.first == 0) {
					// los términos en x se cancelan -> comprobamos si las constantes coinciden
					if (res.second != w) impossible = true;
				} else {
					// podemos resolver para x
					long expected;
					if (res.first == 2) {
						expected = w - res.second;
					} else {
						expected = res.second - w;
					}
					if (currentVal == INF) {
						currentVal = expected;
					} else if (currentVal != expected) {
						// contradicción con el x determinado previamente
						impossible = true;
						return;
					}
				}
			} else {
				// computamos el valor del vecino según la arista: v = w - u
				coeffs.set(v, new Pair(-coeffs.get(u).first, w - coeffs.get(u).second));
				dfs(v);
			}
		}
	}
 
	static void propagate(int u) {
		// una vez conocido x, propagamos los valores reales por la componente
		vis[u] = true;
		for (Pair edge : adj.get(u)) {
			int v = (int)edge.first;
			long w = edge.second;
			if (!vis[v]) {
				ans[v] = w - ans[u];
				propagate(v);
			}
		}
	}
 
	static double findMedian(List<Integer> comp) {
		// el x óptimo minimiza la suma de |ax+b|, que ocurre en la mediana de las raíces
		List<Long> roots = new ArrayList<>();
		for (int node : comp) {
			if (coeffs.get(node).first == 1) {
				roots.add(-coeffs.get(node).second);
			} else {
				roots.add(coeffs.get(node).second);
			}
		}
		Collections.sort(roots);
		int sz = roots.size();
		return (roots.get((sz - 1) / 2) + roots.get(sz / 2)) / 2.0;
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
 
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
 
		adj = new ArrayList<>();
		coeffs = new ArrayList<>();
		vis = new boolean[n];
		ans = new double[n];
		impossible = false;
 
		for (int i = 0; i < n; i++) {
			adj.add(new ArrayList<>());
			coeffs.add(new Pair(-INF, -INF));
		}
 
		// construimos la lista de adyacencia
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			long c = Long.parseLong(st.nextToken());
			adj.get(a).add(new Pair(b, c));
			adj.get(b).add(new Pair(a, c));
		}
 
		List<List<Integer>> components = new ArrayList<>();
		List<Long> componentVals = new ArrayList<>();
 
		// hallamos todas las componentes conexas
		for (int i = 0; i < n; i++) {
			if (!vis[i]) {
				currentComponent = new ArrayList<>();
				currentVal = INF;
				coeffs.set(i, new Pair(1, 0));  // el primer nodo = x
				dfs(i);
				components.add(new ArrayList<>(currentComponent));
				componentVals.add(currentVal);
			}
		}
 
		if (impossible) {
			pw.println("NO");
			pw.close();
			return;
		}
 
		pw.println("YES");
		Arrays.fill(vis, false);
 
		// computamos los valores finales de cada componente
		for (int i = 0; i < components.size(); i++) {
			int start = components.get(i).get(0);
			if (componentVals.get(i) == INF) {
				// x no está fijo -> usamos la mediana para la suma óptima
				ans[start] = findMedian(components.get(i));
			} else {
				// x quedó determinado por un ciclo
				ans[start] = componentVals.get(i) / 2.0;
			}
			propagate(start);
		}
 
		for (int i = 0; i < n; i++) {
			pw.printf("%.1f", ans[i]);
			if (i == n - 1) {
				pw.println();
			} else {
				pw.print(" ");
			}
		}
 
		pw.close();
	}
}