本文主要是介绍spoj1435 - Vertex Cover(贪心or树形dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
暑期个人赛第二场 C - Vertex Cover
是uva10859简化版
题意： 找一个最小点集，使得每条边都能至少找到自己的一个端点，
这道题目前膜拜了两种方法，1-贪心 2-树形DP
贪心
思路：找出每个度为1的点a，找出它的唯一想相邻的节点b，则对于a和b之间的这条边而言，把b放到点集中是较优的决策。然后把点b及和b相连的边都删去，与b相邻节点的度数减1， 这样做是因为把b放到点集中后，与b相连的所有的边都在点集中有了自己的一个端点。所以下次求解就不用考虑这些个点及边。
重复此步骤直到所有点的度数都是0.（此时图中的所有的边都可以在点集中找到自己的端点了）
由于数据量太大，所有用了stl中的vector来存图的边。
代码如下：
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
#define M 100005
vector<int>g[M];
int n, node[M], vis[M];
int main ()
{
scanf("%d",&n);
for(int i = 1; i < n; i++)
{
int u, v;
scanf("%d %d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
node[u]++;
node[v]++;
}
queue<int>q;
for(int i = 1; i <= n; i++)
{
if(node[i]==1)
q.push(i);
}
int ans = 0;
while(!q.empty())
{
int u = q.front();
q.pop();
if(vis[u]||node[u]!=1)
continue;
for(int i = 0; i < (int)g[u].size(); i++)
{
int v = g[u][i];
if(vis[v]==0)
{
vis[v] = 1;//标记删去的节点
ans++;
for(int j = 0; j < (int)g[v].size(); j++)
{
int x = g[v][j];
if(vis[x]==0)
{
node[x]--;
if(node[x]==1)
q.push(x);
}
}
break;
}
}
}
printf("%d\n",ans);
return 0;
}
2、树形dp
状态:dp[i][j]表示从节点i开始且在父亲节点为状态j的条件下能取到灯数的最小值。
状态转移：dp[i][j] = sum{dp[k][1]}(k是i的子节点)【放灯在任何条件下都是合法决策】
dp[i][j] = min(dp[i][j], sum{dp[k][0]})(k是i的子节点)【只有当i是根节点或者i的父亲节点已放灯才成立】
代码如下：
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define M 100005
vector<int>g[M];
int n, dp[M][2], vis[M][2];
int dfs(int x, int y, int f)
{
int &ans = dp[x][y];
if(vis[x][y]) return ans;
vis[x][y] = 1;
ans = 1;
for(int i = 0; i < (int)g[x].size(); i++)
{
int tt = g[x][i];
if(tt!=f)
ans+=dfs(tt, 1, x);
}
if(f<0||y==1)
{
int sum = 0;
for(int i = 0; i < (int)g[x].size(); i++)
{
int tt = g[x][i];
if(tt!=f)
sum+=dfs(tt, 0, x);
}
ans = min(sum,ans);
}
return ans;
}
int main ()
{
int u, v;
scanf("%d",&n);
for(int i = 1; i < n; i++)
{
scanf("%d %d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
memset(vis,0,sizeof(vis));
int ans = 0;
for(int i = 1; i <= n; i++)
if(vis[i][0]==0)
ans += dfs(i,0,-1);
printf("%d\n",ans);
return 0;
}
这篇关于spoj1435 - Vertex Cover(贪心or树形dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
