首页 > 代码库 > UVa 1218 完美的服务
UVa 1218 完美的服务
https://vjudge.net/problem/UVA-1218
题意：
有n台机器形成树状结构。要求在其中一些机器上安装服务器，使得每台不是服务器的计算机恰好和一台服务器计算机相邻。求服务器的最少数量。
思路：
和紫书上前面的UVa1220挺像的，不过这题是一棵无根树，就把0当做根就行了，方法还是一样的dfs。
d[u][0]：u是服务器，则每个子结点可以是服务器也可以不是。
d[u][1]：u不是服务器，但u的父亲是服务器，这意味着u的所有子结点都不是服务器。
d[u][2]：u和u的父亲都不是服务器。这意味着u恰好有一个儿子是服务器。
状态转移方程分析：
d[u][0]：由于它已经是服务器了，所以子结点可以是也可以不是，选择小的，d[u][1]=sum{min(d[v][0],d[v][1])}+1。1代表它自身这个服务器。
d[u][1]：u的父亲是服务器，那么与它相连的就不可能是服务器了，此时很简单，d[u][1]=sum(d[v][2])。
d[u][2]：子结点有且仅有一个服务器，也就是说d[u][2]=min(d[u][2],d[v1][2]+d[v2][2].....+d[v][0])。由于前面已经算出了所有子结点的d[v][2]和，所以这里可以简化为d[u][2]=min(d[u][2],d[u][1]-d[v][2]+d[v][0])。
1 #include<iostream> 2 #include<string> 3 #include<cstring> 4 #include<vector> 5 #include<algorithm> 6 using namespace std; 7 8 const int maxn = 10000 + 5; 9 10 int n, cnt;11 12 vector<int> sons[maxn];13 14 int d[maxn][3];15 16 void dfs(int u,int fa)17 {18 d[u][0] = 1; //加上自身为服务器19 d[u][1] = 0;20 d[u][2] = maxn;21 int k = sons[u].size();22 if (k == 1 && fa != 0) return; //树的叶子节点23 for (int i = 0; i < k; i++)24 {25 int son = sons[u][i];26 if (fa == son) continue;27 dfs(son,u);28 d[u][0] += min(d[son][0], d[son][1]);29 d[u][1] += d[son][2];30 }31 for (int i = 0; i < k; i++)32 {33 int son = sons[u][i];34 if (son == fa) continue;35 d[u][2] = min(d[u][2], d[u][1] - d[son][2] + d[son][0]);36 }37 }38 39 int main()40 {41 //freopen("D:\\txt.txt", "r", stdin);42 int a, b;43 while (cin >> n)44 {45 for (int i = 1; i <= n; i++)46 sons[i].clear();47 for (int i = 1; i < n; i++)48 {49 cin >> a >> b;50 sons[a].push_back(b);51 sons[b].push_back(a);52 }53 dfs(1,0);54 cout << min(d[1][0], d[1][2]) << endl; 55 cin >> a;56 if (a == -1) break;57 }58 return 0;59 }
UVa 1218 完美的服务
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。