YellowStar doit préparer un examen d'anglais dans trois semaiens et a besoin de mémoriser n mots, chacun de longueur m. Il utilise une méthode de mémorisation par association. Pour mémoriser un nouveau mot T :

• Si YellowStar mémorise le mot sans aucune aide, il consomme une énergie égale à la longueur du mot m.
• S'il utilise un mot déjà mémorisé Si, l'énergie consommée est hamming(Si, T) * w, où hamming(Si, T) est la distance de Hamming entre les deux mots (nombre de positions où les caractères diffèrent).

Le but est de minimiser l'énergie totale nécsesaire pour mémoriser tous les mots.

Entrée

L'entrée contient plusieurs jeux de données. Chaque jeu commence par trois entiers n, m et w, suivis de n mots, chacun de longueur m.

Contraintes : 1 ≤ n ≤ 1000, 1 ≤ m, w ≤ 10

Sortie

Pour chaque jeu de données, imprimez l'énergie minimale nécessaire pour mémoriser tous les mots.

Exemple

Entrée:

3 4 2
abch
abcd
efgh

Sortie:

10

Explication: La solution optimale consiste à mémoriser d'abord "abcd" et "efgh" (énergei = 8), puis à utiliser "abcd" pour mémoriser "abch" (énergie = 2). L'énergie totale est 10.

Solution

Ce problème peut être résolu en utilisant l'algorithme de l'arbre couvrant minimal (ACM). On construit un graphe complet où chaque mot est un sommet, et la valeur des arêtes est le minimum entre m et hamming(Si, T) * w. Ensuite, on applique l'algorithme de Kruskal ou Prim pour trouver l'ACM.

Code en C++ (Kruskal)

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;

#define INF 0x3f3f3f3f
#define MAX 1005

struct Edge {
    int u, v;
    int weight;
    bool operator < (const Edge &b) const {
        return weight > b.weight;
    }
};

int n, m, w;
char words[MAX][15];
priority_queue<Edge> edges;
int parent[MAX];

int find(int x) {
    if (x != parent[x])
        parent[x] = find(parent[x]);
    return parent[x];
}

void kruskal() {
    for (int i = 0; i < n; i++)
        parent[i] = i;
    int result = m;
    int count = 1;
    while (!edges.empty()) {
        Edge current = edges.top();
        edges.pop();
        int rootU = find(current.u);
        int rootV = find(current.v);
        if (rootU != rootV) {
            result += current.weight;
            parent[rootU] = rootV;
            count++;
        }
        if (count == n) break;
    }
    printf("%d\n", result);
}

int main() {
    while (scanf("%d%d%d", &n, &m, &w) != EOF) {
        for (int i = 0; i < n; i++)
            scanf("%s", words[i]);
        while (!edges.empty()) edges.pop();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int hammingDistance = 0;
                for (int k = 0; k < m; k++)
                    if (words[i][k] != words[j][k])
                        hammingDistance++;
                edges.push({i, j, min(m, hammingDistance * w)});
            }
        }
        kruskal();
    }
    return 0;
}

Code en C++ (Prim)

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;

#define INF 0x3f3f3f3f
#define MAX 1005

struct Edge {
    int u, v;
    int weight;
    bool operator < (const Edge &b) const {
        return weight > b.weight;
    }
};

int n, m, w;
char words[MAX][15];
int graph[MAX][MAX];
int visited[MAX];
int distance[MAX];

void prim() {
    memset(visited, 0, sizeof(visited));
    visited[0] = 1;
    for (int i = 0; i < n; i++)
        distance[i] = graph[0][i];
    int totalWeight = m;
    int count = 1;
    while (count < n) {
        int minWeight = INF;
        int minIndex = -1;
        for (int i = 0; i < n; i++) {
            if (!visited[i] && distance[i] < minWeight) {
                minWeight = distance[i];
                minIndex = i;
            }
        }
        visited[minIndex] = 1;
        totalWeight += minWeight;
        count++;
        for (int i = 0; i < n; i++) {
            if (!visited[i] && distance[i] > graph[minIndex][i])
                distance[i] = graph[minIndex][i];
        }
    }
    printf("%d\n", totalWeight);
}

int main() {
    while (scanf("%d%d%d", &n, &m, &w) != EOF) {
        for (int i = 0; i < n; i++)
            scanf("%s", words[i]);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                int hammingDistance = 0;
                for (int k = 0; k < m; k++)
                    if (words[i][k] != words[j][k])
                        hammingDistance++;
                graph[i][j] = graph[j][i] = min(m, hammingDistance * w);
            }
        }
        prim();
    }
    return 0;
}