題意：

思路：

注意：

d[u][2]不能設為真的無窮大，因為涉及累加，會溢出。應該設一個它可能取到的最大值n。

然后就是，剛開始用vis數組標記，模擬dfs來遍歷樹，發現不行，因為在求d[u][2]的時候之前的孩子節點已經被標記訪問過了，導致d[u][2]根本算不了，應該在參數列表加一個參數表示父節點。

#include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std;const int N = 1e5+5; vector<int> G[N];int d[N][3], n;void solve(int u, int dad){//printf("%d ",u);//vis[u] = 1;d[u][0] = 1; d[u][1] = 0; d[u][2] = n; // d[u][2]是不可能狀態，否則葉子節點沒有服務器相連了，置為無窮大。 int k = G[u].size();if(k == 0){d[u][2] = 0; return;}for(int i = 0; i < k; ++i){int s = G[u][i];if(s == dad) continue;solve( s, u );// 選 u , 子可選可不選，選代價最少的d[u][0] += min(d[s][0], d[s][1]); // 不選 ud[u][1] += d[s][2]; // 如果u的父親被選了，那么u的兒子都不能選//d[u][2] += min(); }for(int i = 0; i < k; ++i){int s = G[u][i];if(s == dad) continue;d[u][2] = min(d[u][2], d[u][1] + d[s][0] - d[s][2]) ;// 如果u和u的父親都沒被選，那么u的兒子當中一定要有且僅有1個被選。}}int main() {//freopen("in.txt","r",stdin);while(scanf("%d",&n) == 1&&n){for(int i = 1; i <= n; ++i) G[i].clear();//memset(vis,0,sizeof(vis));memset(d,0,sizeof(d));for(int i = 0; i < n-1; ++i){int a,b; scanf("%d %d",&a,&b);G[b].push_back(a); G[a].push_back(b);}solve(1,-1);printf("%d\n",min(d[1][0],d[1][2]));int e; scanf("%d",&e);if(e == -1) break;}return 0; }

總結

以上是生活随笔為你收集整理的UVa1218完美的服务的全部內容，希望文章能夠幫你解決所遇到的問題。

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