Skip to Content
CTRL K

Matching

Solución

Si definimos dp[S]\texttt{dp}[S] como la cantidad de matchings de las mujeres del conjunto SS con los primeros ∣S∣|S| hombres, este problema se reduce a lo siguiente:

dp[S]=∑dp[S\x]:compatible[∣S∣][x] \texttt{dp}[S] = \sum \texttt{dp}[S\backslash x]: \texttt{compatible}[|S|][x]

(Los : significan “tal que”.) En palabras, esto equivale a lo siguiente:

La cantidad de matchings en un subconjunto SS que incluyen a una cierta mujer xx es equivalente a la suma de todos los matchings sin la mujer xx donde la mujer xx es compatible con el ∣S∣|S|-ésimo hombre.

Nuestro caso base es el conjunto vacío, que tiene valor 11 (el conjunto vacío puede considerarse como un único matching que involucra cero pares).

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1e9 + 7;
const int MAX_N = 21;
 
bool compat[MAX_N][MAX_N];
int dp[1 << MAX_N];
 
int main() {
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) { cin >> compat[i][j]; }
	}
 
	dp[0] = 1;
	for (int s = 0; s < (1 << N); s++) {
		int pair_num = __builtin_popcount(s);
		for (int w = 0; w < N; w++) {
			/*
			 * comprobamos que
			 * 1. esta mujer aún no ha sido emparejada
			 * 2. además es compatible con el {pair_num + 1}-ésimo hombre
			 */
			if ((s & (1 << w)) || !compat[pair_num][w]) continue;
 
			// sumamos la cantidad a los estados futuros de DP
			dp[s | (1 << w)] += dp[s];
			dp[s | (1 << w)] %= MOD;
		}
	}
 
	cout << dp[(1 << N) - 1] << endl;
}
import java.io.*;
import java.util.*;
 
public class Main {
	public static final int MOD = (int)1e9 + 7;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		boolean[][] compat = new boolean[N][N];
		for (int m = 0; m < N; m++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int w = 0; w < N; w++) {
				compat[m][w] = (Integer.parseInt(st.nextToken()) == 1);
			}
		}
 
		int[] dp = new int[1 << N];
		dp[0] = 1;
		for (int s = 0; s < (1 << N); s++) {
			int pair_num = Integer.bitCount(s);
			for (int w = 0; w < N; w++) {
				/*
				 * comprobamos que
				 * 1. esta mujer aún no ha sido emparejada
				 * 2. además es compatible con el {pair_num + 1}-ésimo hombre
				 */
				if ((s & (1 << w)) != 0 || !compat[pair_num][w]) continue;
 
				// sumamos la cantidad a los estados futuros de DP
				dp[s | (1 << w)] += dp[s];
				dp[s | (1 << w)] %= MOD;
			}
		}
		System.out.println(dp[(1 << N) - 1]);
	}
}
MOD = 10**9 + 7
MAX_N = 21
 
n = int(input())
 
compat = []
for _ in range(n):
	compat.append(list(map(int, input().split())))
 
dp = [0] * (1 << n)
dp[0] = 1
 
for s in range(1 << n):
	pair_num = bin(s).count("1")
	for w in range(n):
		"""
		comprobamos que
		1. esta mujer aún no ha sido emparejada
		2. es compatible con el {pair_num + 1}-ésimo hombre
		"""
		if (s & (1 << w)) or not compat[pair_num][w]:
			continue
 
		# sumamos el conteo a los estados futuros de DP
		dp[s | (1 << w)] += dp[s]
		dp[s | (1 << w)] %= MOD
 
print(dp[(1 << n) - 1])
Fundamentos