SPOJ：顶点覆盖（PT07X）错误答案

Question

我正在尝试顶点覆盖问题。即使是一个不完美的代码也清除了 soj judge 上的所有案例，但我有一个测试用例（在评论中）失败了，所以我试图删除它。但是，现在它不接受。 Problem Link

问题描述：你必须找到一个加权的无向树的顶点覆盖，即在这棵树中找到一个最小大小的顶点集，使得每条边在该集合中至少有一个端点。

我的算法基于 DFS。早些时候我使用了一个简单的逻辑，即执行 DFS 并在回溯时，如果未包含子顶点，则包含其父顶点（如果尚未包含）。而且，它被接受了。但是，它在具有 6 个顶点的倾斜树的简单情况下失败了。答案应该是2，结果是3。所以，我稍微修改了一下。

我添加了另一个参数来检查一个顶点是否已经被其父节点或子节点覆盖，如果是，则忽略。因此，每当找到一个尚未覆盖的顶点时，我都会在顶点集中添加它的父项。

我的旧源代码：

vector<int> edge[100000]; // to store edges
bool included[100000];    // to keep track of elements in vertex cover set
bool done[100000];        // to keep track of undiscivered nodes to do DFS on tree
int cnt;                  // count the elements in vertex set

/* Function performs DFS and makes a vertex cover set */
bool solve(int source){
  done[source] = true;
  for(unsigned int i = 0; i<edge[source].size(); ++i){
    if(!done[edge[source][i]]){  // if node is undiscovered
      if(!solve(edge[source][i]) && !included[source]){   // if child node is not included and neither its parent
         included[source] = true;    // element added to vertex cover set
         cnt++;                      // increasing the size of set
      }
    }
  }
  return included[source]; // return the status of current source vertex
}

int main(){
  int n,u,v;
  scanint(n);
  for(int i = 0; i<n-1; ++i){
    done[i] = false;
    included[i] = false;
    scanint(u);
    scanint(v);
    edge[u-1].push_back(v-1);
    edge[v-1].push_back(u-1);
  }
  done[n-1] = false;
  included[n-1] = false;
  cnt = 0;
  solve(0);
  printf("%d\n", cnt);
  return 0;
}

我的新源代码：

vector<int> edge[100000];   // to store edges
bool incld[100000];         // to keep track of nodes in vertex cover set
bool covrd[100000];         // to keep track of nodes already covered
bool done[100000];          // to keep track of undiscovered nodes to perform DFS
int cnt;                    // keep track of size of vertex cover set

/* Function to calculate vertex cover set via DFS */
void solve(int source){
  int child;   // to store index of child node
  done[source] = true;
  for(unsigned int i = 0; i<edge[source].size(); ++i){
    if(!done[edge[source][i]]){ // if child node is undiscovered
      child = edge[source][i];  
      if(incld[child])          // if child node is included in vertex set
         covrd[source] = true;  // setting current node to be covered
      else if(!covrd[child] && !incld[source]){ // if child node is not covered and current node is not included in vertex set
         incld[source] = true;     // including current node
         covrd[child] = true;      // covering child node
         cnt++;                    // incrementing size of vertex cover set
      }
    }
  }
}

int main(){
  int n,u,v;
  scanint(n);
  for(int i = 0; i<n-1; ++i){
    done[i] = false;
    incld[i] = false;
    covrd[i] = false;
    scanint(u);
    scanint(v);
    edge[u-1].push_back(v-1);
    edge[v-1].push_back(u-1);
  }
  done[n-1] = false;
  incld[n-1] = false;
  covrd[n-1] = false;
  cnt = 0;
  solve(0);
  printf("%d\n", cnt);
  return 0;
}

请帮忙。

Answer 1

你的第一个解是正确的（你可以找到证明here）。有 6 个顶点的倾斜树的答案实际上是 3（link 中的注释说答案是 2 是错误的）。

SPOJ：顶点覆盖（PT07X）错误答案

SPOJ : Vertex Cover (PT07X) Wrong Answer

algorithm

graph-algorithm