This is a classic dynamic programming problem. We'll need to find minimal vertex cover of an unweighted, undirected tree.

We'll try to find the optimal solution for the subtree rooted at each node considering either its parent is covered (and as such the edge between it and its parent) or its parent is not covered. In the first case, we have the freedom to either cover the current node or not. But in the second case, we must cover the current node. Optimal solution is the one that uses least nodes.

Source code follows -

#include <stdio.h> #include <string.h> #include <vector> using namespace std; #define min(a,b) (((a)<(b))?(a):(b)) #define rep(i,n) for(i=0;i<(n);i++) #define MAXN 100000 vector<int> adj[MAXN+2]; int n; int dp[MAXN+2][2]; int go(int cur, int parent, bool isParentCovered) { if(dp[cur][isParentCovered] != -1) return dp[cur][isParentCovered]; int &ret = dp[cur][isParentCovered]; ret = 0; int i, r; if(isParentCovered) { rep(i, adj[cur].size()) if(adj[cur][i] != parent) { ret += go(adj[cur][i], cur, false); } r = 1; rep(i, adj[cur].size()) if(adj[cur][i] != parent) { r += go(adj[cur][i], cur, true) ; } ret = min(ret, r); } else { ret = 1; rep(i, adj[cur].size()) if(adj[cur][i] != parent) { ret += go(adj[cur][i], cur, true) ; } } return ret; } int main() { int i,u,v; int r1,r2; while(scanf(" %d",&n) == 1) { for(i=1;i<=n;i++) adj[i].clear(); for(i=1;i<n;i++) { scanf(" %d %d",&u,&v); adj[u].push_back(v); adj[v].push_back(u); } memset(dp,-1,sizeof(dp)); r1 = 1; rep(i,adj[1].size()) r1 += go(adj[1][i], 1, true); r2 = 0; rep(i, adj[1].size()) r2 += go(adj[1][i], 1, false); printf("%d\n",min(r1,r2)); } return 0; }

does not work with this input

ReplyDelete6

1 2

2 3

1 4

4 5

5 6

The answer should be 2 and yours outputs 3, I think. Or am i missing something? Thanks

Anyway, it is correct for the judge.

This comment has been removed by the author.

Deletegot it, i was missing something

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteNice code! easy to understand !

ReplyDeletenice code!

ReplyDelete