Solução Informática Avançado - Semana 49

Solução de Lawrence Melo

Vamos usar a seguinte ideia de programação dinâmica com bitmask, $dp[2^{n}][n]$ , onde $dp[mask][i]$ indica o maior caminho da cidade $i$ para a cidade $n - 1$ já tendo visitado as cidades salvas na bitmask. Assim, teremos que:

$dp[mask][i]$ = $\begin{cases} 0 & , \mbox{se i = n - 1} \\ \max\limits_{0 \leq v \leq n - 1} \big( dp[mask | 2^{v}][v] + C[i][v] \big) & , \mbox{caso contrario}\end{cases}$

Checamos sempre se o bit $v$ está ligado ou se existe uma rota entre $i$ e $v$ . A complexidade final é, então, $\mathcal{O}(2^{n} \cdot n^{2})$ .

Código para melhor entendimento:

	#include <bits/stdc++.h>
	using namespace std;
	typedef long long ll;

	const ll MAXN = 20, MAXM = (1 << 18) + 10, INF = (1 << 30);

	ll n, m;
	ll mat[MAXN][MAXN], dp[MAXM][MAXN];

	ll solve(ll bitmask, ll v)
	{

	if(v == n - 1) return dp[bitmask][v] = 0; // Se já estou na cidade n - 1

	if(dp[bitmask][v] != -1) return dp[bitmask][v];

	ll ans = 0;

	for(ll i = 0; i < n; i++)
	{
	if(bitmask & (1 << i) or !mat[v][i]) continue; // se a cidade ja foi visitada ou não existe rota da cidade atual para ela

	ans = max(ans, solve((bitmask \| (1 << i)), i) + mat[v][i]); // calculo o máximo entre todas as rotas possíveis

	}

	if(ans == 0) return dp[bitmask][v] = (-INF); // se da cidade atual não consigo ir para nenhuma outra cidade
	// então a rota é invalida e subtraio infinito para desconsidera-la

	return dp[bitmask][v] = ans;
	}

	int main()
	{
	ios::sync_with_stdio(false), cin.tie(nullptr);

	cin >> n >> m;

	while(m--)
	{
	ll a, b, w;
	cin >> a >> b >> w;
	mat[a][b] = mat[b][a] = max(mat[a][b], w); // sempre escolho a maior rota entre "a" e "b"
	}

	memset(dp, -1, sizeof(dp));

	cout << solve(1, 0) << "\n"; //sempre inicio na cidade 0 e não a visito novamente


	}

view raw

noics49p2.cpp

hosted with ❤ by GitHub

Solução de Lawrence Melo

dp[mask][i] = \begin{cases} 0 & , \mbox{se i = n - 1} \\ \max\limits_{0 \leq v \leq n - 1} \big( dp[mask | 2^{v}][v] + C[i][v] \big) & , \mbox{caso contrario}\end{cases}

$dp[mask][i]$ = $\begin{cases} 0 & , \mbox{se i = n - 1} \\ \max\limits_{0 \leq v \leq n - 1} \big( dp[mask | 2^{v}][v] + C[i][v] \big) & , \mbox{caso contrario}\end{cases}$