Module: Modèles en programmation dynamique - 2


Problem

4 /5


Nain

Theory Click to read/hide

Avis de non-responsabilité : la méthode décrite ci-dessous n'est pas universelle, mais elle peut souvent résoudre un problème ou vous aider à trouver la bonne solution.

Si vous avez besoin de vérifier l'existence d'une permutation dans un problème, ou de trouver le nombre de permutations qui correspondent, ou quelque chose de similaire, alors vous devriez envisager d'utiliser la programmation de sous-ensemble dynamique.

Le paramètre principal sera un masque de bits, qui montrera quels éléments ont déjà été inclus dans la permutation, et lesquels ne le sont pas. Un deuxième paramètre est également souvent requis pour indiquer quel élément a été inclus en dernier.

Souvent, les permutations peuvent être vues dans le contexte des chemins dans les graphes. En conséquence, considérons un exemple classique - le problème du chemin hamiltonien.
Un chemin hamiltonien est un chemin simple qui passe par chaque sommet du graphe exactement une fois. Il peut être représenté simplement comme une permutation de longueur n, où n est le nombre de sommets. L'ordre dans cette permutation indiquera l'ordre dans lequel les sommets de ce chemin sont traversés.

Afin de vérifier la présence d'un chemin hamiltonien dans le graphe, commençons la dynamique dp[mask][last] - existe-t-il un chemin simple qui a contourné les sommets marqués par des uns dans le masque de masque et s'est retrouvé au dernier sommet.
Les valeurs initiales seront dp[2i][i] = vrai, le reste faux, ce qui signifie qu'il y a toujours un chemin vide commençant à l'un des sommets.
Ayant la valeur true dans dp[mask][last] nous ferons des transitions vers l'avant, dans le sens de "prolonger le chemin". C'est-à-dire que nous allons chercher les nombres de sommets qui sont marqués de zéro dans le masque (nous ne les avons pas encore visités en chemin) et en même temps tels qu'il y a une arête du dernier à ce sommet (le chemin doit être prolongé par un bord existant). Autrement dit, nous faisons dp[mask | 2k][k] = vrai si dp[masque][dernier] = vrai ET masque & 2k = 0 (le sommet k n'a pas encore été visité) Et il y a une arête last -> k.
En fin de compte, un chemin hamiltonien existe s'il existe une vraie valeur dans dp pour les paramètres du masque de bits tout-un et de tout dernier sommet.

Problem

Une fois, le nain Quark est tombé sur une carte au trésor. Il y a N points marqués sur la carte où le trésor peut être trouvé. Tous les points sont numérotés de 1 à N. Pour chaque paire de points, Quark connaît la longueur de la route qui les relie. Quark commence sa recherche à partir du point numéro 1. Avant de commencer son long voyage, le nain rusé barre des points où, à son avis, il ne peut y avoir de trésor. Il est garanti que le point numéro 1 n'est jamais barré. Après cela, Quark choisit un itinéraire qui passe par tous les points restants sur la carte. L'itinéraire ne passe pas plus d'une fois par le même point. Un quark ne peut marcher que sur des routes qui relient des points non croisés.

Quark veut choisir un itinéraire de longueur minimale. Il est nécessaire de trouver un tel itinéraire pour Quark.

Entrée
La première ligne contient un entier N (1 ≤ N ≤ 15) — le nombre de points marqués sur la carte. Les N lignes suivantes contiennent les distances entre les points. La (i+1)-ème ligne contient N entiers di1,di2, diN — longueurs de routes du i-ème point à tous les autres. Il est garanti que dij=dji, dii=0 et 0 <dij < 100 . La (N+2)ème ligne contient un entier Q (1 < Q ≤ 1000) — le nombre d'options de suppression de points pour cette carte. Les lignes Q suivantes contiennent une description des options de suppression. La description commence par le chiffre C (0 ≤ C < N) — le nombre de points où, selon Quark, le trésor ne peut pas être. Les nombres C suivants donnent les numéros de ces points.

Mentions légales
Imprimer les lignes Q. Dans chaque ligne, écrivez un entier — la longueur de l'itinéraire minimum avec l'option correspondante de suppression de points.
Exemples
# Entrée Sortie
1 3
0  45 10
45 0  30
10 30 0
2
0
1 3 		40
45
2 5
0  14 20 17 14
14 0  15 19 18
20 15 0  15 16
17 19 15 0  14
14 18 16 14 0
2
3 5 4 3
0		 14
58

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!