Encuentre el árbol de expansión mínimo con bordes de colores alternos

Dado un gráfico con N Nodes y M aristas donde cada arista tiene un color (ya sea negro o verde) y un costo asociado. Encuentre el árbol de expansión mínimo del gráfico de modo que cada ruta en el árbol esté formada por bordes de colores alternos.

Ejemplos:

Entrada: N = 3, M = 4

Salida: 6

Entrada: N = 4, M = 6

Salida: 4

Acercarse:

• La primera observación que hacemos aquí es que cada tipo de árbol de expansión será una string. Para probarlo, supongamos que tenemos un árbol que no es una string y cada camino en él está formado por aristas alternas. Entonces podemos deducir que al menos 1 Node tiene un grado de 3. De estos 3 bordes, al menos 2 tendrán el mismo color. El camino que usa estos 2 bordes nunca seguirá las condiciones y, por lo tanto, este tipo de árbol siempre es una string.
• Ahora podemos encontrar una string con un costo mínimo y bordes alternos usando bitmask-dp,
  dp[mask(2^n)][Node(n)][col_of_last_edge(2)] donde la máscara es la máscara de bits de los Nodes que hemos agregado a la string Node es el último Node que agregamos a la string. col_of_last_edge es el color del uso del borde para conectar Node.
• Para hacer la transición de 1 estado a otro estado, visitamos la lista de adyacencia del último Node y usamos los bordes que tienen el color != col_of_last_edge.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the
// above approach
#include <bits/stdc++.h>
using namespace std;
  
int graph[18][18][2];
  
// Initializing dp of size =
// (2^18)*18*2.
long long dp[1 << 18][18][2];
  
// Recursive Function to calculate
// Minimum Cost with alternate 
// colour edges
long long minCost(int n, int m, int mask, int prev, int col)
{
    // Base case
    if (mask == ((1 << n) - 1)) {
        return 0;
    }
    // If already calculated
    if (dp[mask][prev][col == 1] != 0) {
        return dp[mask][prev][col == 1];
    }
  
    long long ans = 1e9;
  
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2; j++) {
            // Masking previous edges
            // as explained in above formula.
            if (graph[prev][i][j] && !(mask & (1 << i)) 
                && (j != col)) {
                long long z = graph[prev][i][j] + 
                              minCost(n,m,mask|(1<<i),i,j);
                ans = min(z, ans);
            }
        }
    }
  
    return dp[mask][prev][col == 1] = ans;
}
  
// Function to Adjacency
// List Representation 
// of a Graph
void makeGraph(vector<pair<pair<int,int>,
                      pair<int,char>>>& vp,int m){
  
  for (int i = 0; i < m; i++) {
    int a = vp[i].first.first - 1;
    int b = vp[i].first.second - 1;
    int cost = vp[i].second.first;
    char color = vp[i].second.second;
    graph[a][b][color == 'W'] = cost;
    graph[b][a][color == 'W'] = cost;
  }
}
  
// Function to getCost
// for the Minimum Spanning
// Tree Formed
int getCost(int n,int m){
      
    // Assigning maximum
    // possible value.
    long long ans = 1e9;
  
    for (int i = 0; i < n; i++) {
        ans = min(ans, minCost(n, m, 1 << i, i, 2));
    }
  
    if (ans != 1e9) {
        return ans;
    }
    else {
        return -1;
    }
}
  
// Driver code
int main()
{
    int n = 3, m = 4;
    vector<pair<pair<int, int>, pair<int, char> > > vp = {
        { { 1, 2 }, { 2, 'B' } },
        { { 1, 2 }, { 3, 'W' } },
        { { 2, 3 }, { 4, 'W' } },
        { { 2, 3 }, { 5, 'B' } }
    };
  
    makeGraph(vp,m);
    cout << getCost(n,m) << '\n';
      
    return 0;
}

# Python implementation of the approach
  
graph = [[[0, 0] for i in range(18)] for j in range(18)]
  
# Initializing dp of size =
# (2^18)*18*2.
dp = [[[0, 0] for i in range(18)] for j in range(1 << 15)]
  
# Recursive Function to calculate
# Minimum Cost with alternate
# colour edges
def minCost(n: int, m: int, mask: 
            int, prev: int, col: int) -> int:
    global dp
  
    # Base case
    if mask == ((1 << n) - 1):
        return 0
  
    # If already calculated
    if dp[mask][prev][col == 1] != 0:
        return dp[mask][prev][col == 1]
  
    ans = int(1e9)
  
    for i in range(n):
        for j in range(2):
  
            # Masking previous edges
            # as explained in above formula.
            if graph[prev][i][j] and not (mask & (1 << i)) \
                and (j != col):
                z = graph[prev][i][j] + minCost(n,
                        m, mask | (1 << i), i, j)
                ans = min(z, ans)
  
    dp[mask][prev][col == 1] = ans
    return dp[mask][prev][col == 1]
  
# Function to Adjacency
# List Representation
# of a Graph
def makeGraph(vp: list, m: int):
    global graph
    for i in range(m):
        a = vp[i][0][0] - 1
        b = vp[i][0][1] - 1
        cost = vp[i][1][0]
        color = vp[i][1][1]
        graph[a][b][color == 'W'] = cost
        graph[b][a][color == 'W'] = cost
  
# Function to getCost
# for the Minimum Spanning
# Tree Formed
def getCost(n: int, m: int) -> int:
  
    # Assigning maximum
    # possible value.
    ans = int(1e9)
    for i in range(n):
        ans = min(ans, minCost(n, m, 1 << i, i, 2))
  
    if ans != int(1e9):
        return ans
    else:
        return -1
  
# Driver Code
if __name__ == "__main__":
  
    n = 3
    m = 4
    vp = [[[1, 2], [2, 'B']],
        [[1, 2], [3, 'W']],
        [[2, 3], [4, 'W']],
        [[2, 3], [5, 'B']]]
    makeGraph(vp, m)
    print(getCost(n, m))
  
# This code is contributed by
# sanjeev2552

6

Complejidad de tiempo: O(2^N * (M + N))