Tug of War

Análisis oficial 

Armar ciclos

Imaginemos que tenemos un grafo bipartito donde cada puesto es un nodo y cada persona es una arista entre los dos puestos que está dispuesta a ocupar.

Si algún nodo tiene grado igual a 0, entonces no es posible asignar los equipos.

Si algún nodo tiene grado igual a 1, entonces debemos asignarle la persona dispuesta a ocupar ese puesto. Después de asignar a esa persona, podemos borrar el nodo y la arista del grafo.

Podemos asignar personas de forma repetida y borrar nodos de grado igual a 1 usando un BFS. Después de hacer esto, todos los nodos tendrán grado mayor que 1.

Sin embargo, si algún nodo tiene grado mayor que 2, entonces por el principio del palomar debe haber un nodo con grado menor que 2, lo cual no es posible.

Así, nos quedan varios ciclos simples disjuntos. Como este es un grafo bipartito, las longitudes de estos ciclos son todas pares.

Usar DP de mochila

Sea $C$ el conjunto de todos los ciclos y sea $d$ la diferencia de fuerzas de los nodos que borramos previamente.

Consideremos un solo ciclo. Nótese que si una persona/arista se asigna a un lado, entonces la siguiente persona debe asignarse al lado opuesto.

¡Esto significa que cada ciclo aporta una cantidad fija a la diferencia de fuerzas! Sea $V_i$ el valor absoluto de esta cantidad para el $i$-ésimo ciclo.

Ahora solo hay que comprobar si existen 2 conjuntos disjuntos $S$ y $T$ tales que $S \cup T = C$ y

Esto es lo mismo que comprobar si existe un subconjunto $S$ de $C$ tal que

Podemos comprobar esto usando DP de mochila en tiempo $\mathcal{O}(NK)$.

Como solo estamos comprobando si podemos obtener algún valor, podemos usar un bitset para acelerar esto.

La complejidad final es $\mathcal{O}(NK / 64)$, que es suficientemente rápida para 100 puntos.

Implementación

#include <bits/stdc++.h>
using namespace std;
 
multiset<pair<int, int>> graph[60001];
bool visited[60001];
bitset<600001> possible;
int tot = 0, sm = 0;
 
void dfs(int node) {
	visited[node] = true;
	if (!graph[node].size()) return;
	int nxt, cost;
	tie(nxt, cost) = *graph[node].begin();
 
	tot += cost;
	if (!visited[nxt]) {
		graph[nxt].erase(graph[nxt].find({node, -cost}));
		graph[node].clear();
		dfs(nxt);
	}
}
 
int main() {
	int n, k;
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= 2 * n; i++) {
		int l, r, s;
		scanf("%d %d %d", &l, &r, &s);
		graph[l].insert({n + r, s});
		graph[n + r].insert({l, -s});
	}
 
	queue<int> q;
	for (int i = 1; i <= 2 * n; i++) {
		if (graph[i].size() == 1) q.push(i);
		if (graph[i].size() == 0) return printf("NO\n"), 0;
	}
	while (q.size()) {
		int curr = q.front();
		q.pop();
		if (graph[curr].size() == 0) return printf("NO\n"), 0;
		int nxt, cost;
		tie(nxt, cost) = *graph[curr].begin();
		tot += cost;
 
		graph[curr].clear();
		graph[nxt].erase(graph[nxt].find({curr, -cost}));
		if (graph[nxt].size() == 1) q.push(nxt);
	}
 
	vector<int> items;
	if (tot) items.push_back(abs(tot));
	for (int i = 1; i <= 2 * n; i++)
		if (!visited[i] && graph[i].size()) {
			tot = 0;
			graph[i].erase(graph[i].begin());
			dfs(i);
			if (tot) items.push_back(abs(tot));
		}
	sm = accumulate(items.begin(), items.end(), 0);
 
	possible[0] = 1;
	for (int i : items) possible |= possible << i;
	for (int i = 0; i <= sm; i++)
		if (possible[i] && abs(2 * i - sm) <= k) return printf("YES\n"), 0;
	printf("NO\n");
	return 0;
}