// uva 1218 Perfect Service 樹形dp // // 解題思路: // // d[u][0]表示節點本身是服務器 // d[u][1]表示節點的父節點是服務器 // d[u][2]表示節點的孩子是服務器 // d[u][0] = sigma(d[v][0],d[v][1]); // 自己是服務器,那么孩子可以是服務器 // // 也可以不是服務器 // d[u][1] = sigma(d[v][2]); // 父親是服務器,那么本身就不用了,只要孩子 // // 的孩子是服務器.這樣是最優的 // d[u][2] = min(d[u][1] - d[v][2] + d[v][0]) // 只要一個孩子是服務器就可以了 // // 整體感悟: // // 這道題看了很久很久,有一年了吧,對于d[u][0]很好理解,d[u][1]也挺好理解 // 對于d[u][2]理解一直不夠,但是忽然就恍然大悟,只要一個孩子節點的孩子有服務器就 // 可以啦,其他都不必.過程是很痛苦的,但是最后發現自己理解以后,還是挺好理解的 // 繼續加油吧~~~~FIGHTING!!!#include <cstring> #include <algorithm> #include <iostream> #include <cstdio> #include <cmath> #include <string> #include <vector> #include <queue> #define For(x,a,b,c) for (int x = a; x <= b; x += c) #define Ffor(x,a,b,c) for (int x = a; x >= b; x -= c) #define cls(x,a) memset(x,a,sizeof(x)) using namespace std; typedef long long ll;const double PI = acos(-1.0); const double EPS = 1e-10; const int MAX_N = 10000 + 8; const int INF = 10009; int N,M;vector<int> g[MAX_N]; int d[MAX_N][3];void input(){for (int i = 1;i <= N;i ++)g[i].clear();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);} }void DP(int u,int fa){d[u][0] = 1;d[u][1] = 0;d[u][2] = INF;for (int i = 0;i < g[u].size(); i++){int v = g[u][i];if (v == fa)continue;DP(v,u);d[u][0] += min(d[v][0],d[v][1]);d[u][1] += d[v][2];}for (int i = 0 ; i< g[u].size();i ++){int v = g[u][i];if (v == fa)continue;d[u][2] = min(d[u][2],d[u][1] - d[v][2] + d[v][0]);}}void solve(){DP(1,-1);printf("%d\n",min(d[1][0],d[1][2])); }int main(){//freopen("1.in","r",stdin);while(scanf("%d",&N)){input();solve();int x;scanf("%d",&x);if (x == -1)break;}return 0; }

總結

以上是生活随笔為你收集整理的uva 1218 Perfect Service 树形dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。