動的プログラムを使用して最小限のエッジカバーを見つける効率的な方法

Question

セルフループと平行エッジのない無向グラフを指定します。

私の目的はminimum edge coverです。私はそれがbitmask DPを使用して効率的に行うことができることを知りました。私はたくさん試しましたが、state of DPの定義方法を理解することができません。 DPの状態を決定する際にお手伝いください。

dp[u][hashGuard] // curerntly in u node, this depicts minimum guards required for rest of the nodes encountered later 

トランジション機能 - -

Answer 1

私は、ビットマスクを使用して実装されていませんでした、私の動的なプログラミングアプローチは、2つの状態がありここで

// In node u, we have no guards, so we must have to put guards on adjacent nodes 
dp[u][0] += dp[v][1] for all adjacent nodes v from u 

// In current node u, we have guard. So we can try to minimize the number of guards by puting guards on adjacent nodes or by not putting 
dp[u][1] += min(dp[v][1], dp[v][0]) for all adjacent nodes v from u 

を私のC++実装です -

// Assuming the graph is a tree. you can transform it for graph by using a visited flag instead of parent array 
#define MAX 100001 

int dp[MAX << 2][2]; 
int parent[MAX]; 
vector <int> adj[MAX]; 

int minVertexCover(int node, bool hasGuard) { 

    if((int)adj[node].size() == 0) return 0; 
    if(dp[node][hasGuard] != -1) return dp[node][hasGuard]; 

    int sum = 0; 
    for(int i = 0; i < (int)adj[node].size(); i++) { 
     int v = adj[node][i]; 
     if(v != parent[node]) { 
      parent[v] = node; 
      if(!hasGuard) { 
       sum += minVertexCover(v, true); 
      } else { 
       sum += min(minVertexCover(v, false), minVertexCover(v, true)); 
      } 
     } 
    } 
    return dp[node][hasGuard] = sum + hasGuard; 
} 

/* 
usage: 
// graph input 
// if node 1 and node 2 connected, then 
// adj[2].push_back(1); 
// adj[1].push_back(2) 

result = min(minVertexCover(1, false), minVertexCover(1, true)); 
if(n > 1) 
    printf("%d\n", result); 
else 
    printf("1\n"); 
*/