UVa 1218 Perfect Service 完美的服务

***状态设计值得一看
dp[u][0]表示u是服务器(以下v均指任意u的子结点,son指u的所有子结点)
ap[u][0]=sum{dp[v][1]}+1//错误,服务器是可以和其他服务器相邻的
dp[u][0]=sum{min(dp[v][0],dp[v][1])}+1
dp[u][1]表示u不是服务器,但是父亲是,显然子结点不是
dp[u][1]=sum{dp[v][2]}
dp[u][2]表示u和父亲都不是服务器,但自身有一个子结点是
此情况-1表示不可能满足
***dp[u][2]=min{dp[v][0]}//错误,别犯傻,怎么能忽略其他子结点需要的服务器
dp[u][2]=min{dp[v][0]+sum{dp[x][2]}}(x∈son-i)
=sum{dp[v][2]}-max{dp[v][2]-dp[v][0]}
=dp[u][1]+min{dp[v][0]-dp[v][2]}
(以上"表示..."均指"表示...的情况总数")

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int dp[10010][3];
 6 bool vis[10010];
 7 //int vis2[20010];
 8 struct Edge
 9 {
10     int to,next;
11 }edge[20100];
12 int num_edge,n,first[10100];
13 //void dfs(int x)
14 //{
15 //    int k=first[x];
16 //    while(k!=0)
17 //    {
18 //        if(vis2[k]==0)
19 //        {
20 //            vis2[k]=1;
21 //            vis2[edge[k].p]=-1;
22 //            dfs(edge[k].to);
23 //        }
24 //        k=edge[k].next;
25 //    }
26 //}
27 void dfs2(int u)
28 {
29     vis[u]=true;
30     dp[u][0]=1;
31     dp[u][1]=0;
32     int k=first[u],v;
33     while(k!=0)
34     {
35         v=edge[k].to;
36         if(!vis[v])
37         {
38             dfs2(v);
39             dp[u][0]+=min(dp[v][0],dp[v][1]);
40             dp[u][1]+=dp[v][2];
41             dp[u][2]=min(dp[u][2],dp[v][0]-dp[v][2]);
42         }
43         k=edge[k].next;
44     }
45     dp[u][2]+=dp[u][1];
46 }
47 //void print(int x)
48 //{
49 //    printf("%d ",x);
50 //    int k=first[x];
51 //    while(k!=0)
52 //    {
53 //        if(vis2[k]==1)
54 //        {
55 //            print(edge[k].to);
56 //        }
57 //        k=edge[k].next;
58 //    }
59 //}
60 int main()
61 {
62     int t,i,a,b;
63     while(n!=-1)
64     {
65         scanf("%d",&n);
66         num_edge=0;
67         memset(vis,0,sizeof(vis));
68         memset(first,0,sizeof(first));
69         memset(dp,0x01,sizeof(dp));
70         for(i=1;i<n;i++)
71         {
72             scanf("%d%d",&a,&b);
73             edge[++num_edge].to=b;
74             edge[num_edge].next=first[a];
75             first[a]=num_edge;
76             //edge[num_edge].p=num_edge+1;
77             edge[++num_edge].to=a;
78             edge[num_edge].next=first[b];
79             first[b]=num_edge;
80             //edge[num_edge].p=num_edge-1;
81         }
82         //dfs(1);
83         //print(1);
84         dfs2(1);
85 //        t=min(dp[1][0],dp[1][1]);
86 //        if(dp[1][2]!=-1)//不需要给dp[][2]加负一的特判,只需要保持在不可能时把值设为非常大的值(Maxn)即可
87 //            t=min(t,dp[1][2]);//错的,根结点不能为自己和父亲都是服务器,因为没有父亲
88         printf("%d
",min(dp[1][0],dp[1][2]));
89         scanf("%d",&n);
90     }
91     return 0;
92 }
原文地址:https://www.cnblogs.com/hehe54321/p/7300268.html