LightOJ1201 A Perfect Murder（树形DP）

一道经典的树型DP入门题。dp[u][0/1]表示u点不选或选时以u为根的子树最多能选择的点数。

题目给的有向有环图可以看作森林，注意不是树，因为题目没有说图是连通的！

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define MAXN 1111
 6 #define MAXM 1111*1111
 7 struct Edge{
 8     int v,next;
 9 }edge[MAXM];
10 int NE,head[MAXN];
11 void addEdge(int u,int v){
12     edge[NE].v=v; edge[NE].next=head[u]; head[u]=NE++;
13 }
14 int d[MAXN][2];
15 int dfs(int u,int k,int fa){
16     if(d[u][k]!=-1) return d[u][k];
17     int res=k;
18     for(int i=head[u]; i!=-1; i=edge[i].next){
19         int v=edge[i].v;
20         if(v==fa) continue;
21         if(k) res+=dfs(v,0,u);
22         else res+=max(dfs(v,0,u),dfs(v,1,u));
23     }
24     return d[u][k]=res;
25 }
26 int par[MAXN];
27 int Find(int a){
28     while(a!=par[a]){
29         par[a]=par[par[a]];
30         a=par[a];
31     }
32     return a;
33 }
34 void Union(int a,int b){
35     int pa=Find(a),pb=Find(b);
36     if(pa==pb) return;
37     par[pb]=pa;
38 }
39 int main(){
40     int t,n,m,a,b;
41     scanf("%d",&t);
42     for(int cse=1; cse<=t; ++cse){
43         NE=0;
44         memset(head,-1,sizeof(head));
45         scanf("%d%d",&n,&m);
46         for(int i=1; i<=n; ++i) par[i]=i;
47         while(m--){
48             scanf("%d%d",&a,&b);
49             addEdge(a,b); addEdge(b,a);
50             Union(a,b);
51         }
52         memset(d,-1,sizeof(d));
53         int res=0;
54         for(int i=1; i<=n; ++i){
55             if(par[i]==i) res+=max(dfs(i,0,0),dfs(i,1,0));
56         }
57         printf("Case %d: %d
",cse,res);
58     }
59     return 0;
60 }