题面:http://poj.org/problem?id=3398
本题是求树的最小支配集裸题。
Code:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
using namespace std;
const int N=10005,INF=0x3f3f3f3f;
struct Edge{
int v,Next;
}Edge[N];
int head[N],Cnt;
int f[N][3];
void Push(int u,int v){
Edge[Cnt].v=v;
Edge[Cnt].Next=head[u];
head[u]=Cnt++;
}
void dfs(int u,int fa){
f[u][2]=0;
f[u][0]=1;
int s=0,sum=0,inc=INF;
for(int i=head[u];i!=-1;i=Edge[i].Next){
int v=Edge[i].v;
if(v==fa){
continue;
}
dfs(v,u);
f[u][0]+=min(f[v][0],f[v][2]);
if(f[v][0]<=f[v][1]){
sum+=f[v][0];
s=1;
}
else{
sum+=f[v][1];
inc=min(inc,f[v][0]-f[v][1]);
}
if(f[v][1]!=INF && f[u][2]!=INF){
f[u][2]+=f[v][1];
}
else{
f[u][2]=INF;
}
if(inc==INF&&!s){
f[u][1]=INF;
}
else{
f[u][1]=sum;
if(!s){
f[u][1]+=inc;
}
}
}
}
int main(){
int n,u,v,opt;
while(scanf("%d",&n)!=EOF){
Cnt=1;
memset(head,-1,sizeof(head));
for(int i=0;i<n-1;i++){
scanf("%d%d",&u,&v);
Push(u,v);
Push(v,u);
}
for(int i=0;i<=n;i++){
for(int j=0;j<=2;j++){
f[i][j]=INF;
}
}
dfs(1,-1);
int ans=min(f[1][0],f[1][1]);
printf("%d\n",ans);
scanf("%d",&opt);
if(opt==-1){
break;
}
}
return 0;
}