Blazing New Trails

Explicación

Nos dan n lugares de interés y m senderos posibles entre ellos. Entre estos lugares, k están marcados como especiales. Cada sendero conecta dos lugares y tiene un cierto costo.

El objetivo es construir senderos de modo que:

• Todo lugar quede conectado con todos los demás.
• Haya exactamente un camino entre cualquier par de lugares.
• Exactamente w senderos conecten un lugar especial y un lugar regular.
• El costo total de los senderos elegidos se minimice.

Resolver sin aristas especiales

Si ignoramos la restricción sobre las aristas especial–regular, el problema se reduce simplemente a hallar un árbol de expansión mínima (MST), que se puede resolver con el algoritmo de Kruskal y un DSU.

Tratar las aristas especiales con relajación lagrangiana

Para controlar el número de aristas especial–regular en el árbol de expansión, introducimos un parámetro λ. Para cada arista que conecta un nodo especial con uno regular, modificamos temporalmente su costo sumándole λ.

Así el costo modificado queda:

cost' = cost + λ * type

donde type = 1 si la arista conecta un nodo especial y uno regular, y 0 en caso contrario.

Si λ es grande, las aristas especiales se vuelven caras y el MST incluirá menos de ellas. Si λ es pequeño o negativo, las aristas especiales se vuelven más baratas y el MST incluirá más. Esto significa que el número de aristas especiales elegidas en el MST cambia de forma monótona con λ.

Por este comportamiento, podemos hacer búsqueda binaria sobre λ:

• Ejecutar el MST con los costos modificados.
• Contar cuántas aristas especiales aparecen en el árbol resultante.
• Si el conteo es al menos w, aumentamos λ.
• En caso contrario, disminuimos λ.

Finalmente hallamos el mayor λ tal que el MST todavía contiene al menos w aristas especiales. Como añadimos λ a cada una de esas aristas de forma artificial, restamos w * λ del costo final para recuperar el costo mínimo real.

Comprobación de imposibilidad

Antes de la búsqueda binaria, debemos verificar si un árbol de expansión con exactamente w aristas especiales es siquiera estructuralmente posible. Si la geometría del grafo nos obliga a usar más o menos aristas especiales solo para mantener el grafo conexo, nuestra búsqueda binaria empujará λ al infinito y producirá un resultado incorrecto.

Para evitarlo, determinamos los extremos absolutos del número de aristas especiales que puede contener cualquier árbol de expansión válido:

• Máximo de aristas especiales: ejecutar el algoritmo de Kruskal priorizando estrictamente las aristas especiales sobre las regulares.
• Mínimo de aristas especiales: ejecutar el algoritmo de Kruskal priorizando estrictamente las aristas regulares sobre las especiales.

Si el grafo no se puede conectar por completo, o si w cae estrictamente fuera de este rango [min, max], es imposible. Inmediatamente imprimimos -1 y terminamos antes de cualquier búsqueda binaria.

Implementación

Complejidad temporal: $\mathcal{O}((m \log m + m \alpha(n)) \cdot \log C)$

 
#include <bits/stdc++.h>
using namespace std;
 
// BeginCodeSnip{DSU for Kruskal}
struct DSU {
	int n, cc;
	vector<int> par, rnk;
 
	void init(int _n) {
		n = cc = _n;
		rnk.assign(n + 5, 1);
		par.resize(n + 5);
		iota(par.begin(), par.end(), 0);
	}
 
	int find(int v) { return par[v] = (par[v] == v ? v : find(par[v])); }
 
	bool unite(int a, int b) {
		a = find(a);
		b = find(b);
 
		if (a == b) return false;
 
		if (rnk[a] < rnk[b]) swap(a, b);
 
		par[b] = a;
		rnk[a] += rnk[b];
		cc--;
 
		return true;
	}
};
// EndCodeSnip
 
long long n, m, k, w, x, a, b, c;
vector<array<long long, 4>> edges;
DSU dsu;
 
// BeginCodeSnip{Solve for a Lambda}
pair<long long, long long> solve(long long lambda) {
 
	for (auto &e : edges) e[0] += -e[1] * lambda;
 
	sort(edges.begin(), edges.end());
 
	dsu.init(n);
 
	long long total = 0, cnt = 0;
 
	for (auto e : edges) {
		if (dsu.unite(e[2], e[3])) {
			total += e[0];
			cnt += -e[1];
		}
	}
 
	for (auto &e : edges) e[0] -= -e[1] * lambda;
 
	return {total, cnt};
}
// EndCodeSnip
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	cin >> n >> m >> k >> w;
	vector<bool> special(n, false);
 
	long long lo = -200005, hi = 200005, mid;
 
	// BeginCodeSnip{Get and Store input}
	for (int i = 0; i < k; ++i) {
		cin >> x;
		--x;
		special[x] = true;
	}
 
	edges.resize(m);
 
	for (int i = 0; i < m; ++i) {
		cin >> a >> b >> c;
		--a;
		--b;
		edges[i] = {c, -(special[a] ^ special[b]), a, b};
	}
	// EndCodeSnip
 
	// BeginCodeSnip{Impossibility Check}
 
	long long min_special = solve(hi).second;
	long long max_special = solve(lo).second;
 
	// Si el grafo está desconectado, dsu.cc será > 1 después de solve()
	if (dsu.cc > 1 || w < min_special || w > max_special) {
		cout << -1 << "\n";
		return 0;
	}
	// EndCodeSnip
 
	// BeginCodeSnip{Lagrangian Relaxation}
	while (lo + 1 < hi) {
		mid = (lo + hi) / 2;
		if (solve(mid).second >= w) lo = mid;
		else hi = mid;
	}
	// EndCodeSnip
 
	auto ans = solve(lo);
 
	cout << ans.first - w * lo << "\n";
}