每个节点上可以站士兵守卫道路。
问要守卫所有的道路至少要多少个士兵。
跟那个
poj 2342 Anniversary party(简单树形dp+dfs)
真是像极了。。。
我就是根据那个来写的。。。
思路如下：
如果当前节点站士兵，则以它为父亲的子节点（就是它的邻接点）就可以站或者不站，取
两种情况中消耗最小的。 dp[i][1]+=min(dp[v][1],dp[v][0])
如果当前节点不站士兵，则它的邻接点不能被守卫到，故它的邻接点必须要有士兵。
dp[i][0]+=dp[v][1];
v是i的邻接点。
吐槽一下啦+ +
hdu 数据比poj 弱。。。。我开始用vector写，poj 上死活都是mle
后来看了别人的提醒，改成邻接表存，就AC了。。。
加边的时候当无向边处理。所以不要忘了add(b,a)!!
邻接表版本yoha !
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
struct edge
{
int to;
int next;
}w[10010];
bool vis[1510];
int dp[1510][2],head[1510],tot;
void add(int x,int y)
{
w[tot].to=y;
w[tot].next=head[x];
head[x]=tot++;
}
void dfs(int r)
{
vis[r]=true;
int v,i;
for(i=head[r];i;i=w[i].next)
{
v=w[i].to;
if(!vis[v])
{
dfs(v);
dp[r][0]+=dp[v][1];
dp[r][1]+=min(dp[v][1],dp[v][0]);
}
}
}
int main()
{
int n,m,a,b;
while(scanf("%d",&n)!=EOF)
{
memset(vis,0,sizeof(vis));
memset(head,0,sizeof(head));
tot=1;
for(int i=0;i<n;i++)
{
dp[i][0]=0;
dp[i][1]=1;
}
for(int i=0;i<n;i++)
{
scanf("%d:(%d)",&a,&m);
for(int i=0;i<m;i++)
{
scanf("%d",&b);
add(a,b);
add(b,a);
}
}
dfs(0);
printf("%d\n",min(dp[0][0],dp[0][1]));
}
return 0;
}
只在hdu过的了的vector版本~~~~~= =
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
vector<int> t[1510];
bool vis[1510];
int dp[1510][2];
void dfs(int r)
{
vis[r]=true;
int v;
int s=t[r].size();
for(int i=0;i<s;i++)
{
v=t[r][i];
if(!vis[v])
{
dfs(v);
dp[r][0]+=dp[v][1];
dp[r][1]+=min(dp[v][1],dp[v][0]);
}
}
//dp[r][1]+=1;
}
int main()
{
int n,m,a,b;
while(scanf("%d",&n)!=EOF)
{
memset(t,0,sizeof(t));
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
t[i].clear();
for(int i=0;i<n;i++)
{
dp[i][0]=0;
dp[i][1]=1;
}
//memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
{
scanf("%d:(%d)",&a,&m);
for(int i=0;i<m;i++)
{
scanf("%d",&b);
t[a].push_back(b);
t[b].push_back(a);
}
}
dfs(0);
printf("%d\n",min(dp[0][0],dp[0][1]));
}
return 0;
}