POJ终于修好啦

题意

和UVA1205是同一题，在洛谷上是紫题

有一棵树，需要给其所有节点染色，每个点染色所需的时间是一样的都是11.给每个点染色，还有一个开销“当前时间×ci×ci”，cici是每个节点的一个权值。(当前时间是染完这个节点的时间)  染色还有另一个约束条件，要染一个点必须要先染好其父节点，所以第一个染的点是根节点.  求最小开销。

思路

这道题显然对于 每一个可选的子节点选最重的 的贪心思路是错误的

就有点类似动态规划了 不过不DP也是可以贪心出来的。但是这个策略比较麻烦。大致思路就是父节点和子节点经过一些操作合并，合并之后贪心就是没问题的了。

不过我一开始自己的思路就是类似并查集+贪心的，不是合并（虽然差不多），就是全局贪心，把所有的点的权值排序，然后最大到最小的所有点慢慢并查集搜回去，直到所有点被处理过，也应该是可以的吧？但是时间复杂度肯定不行，于是就看李煜东的代码了（颓）。

Code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 1005 int n, r; double c[N]; int nxt[N], la[N], num[N],fa[N]; double d[N],tot[N]; bool vis[N]; void color_a_tree() { for (int i = 1; i <= n; i++) { scanf("%lf", &c[i]); nxt[i] = i; la[i] = i; num[i] = 1; tot[i] = c[i]; } memcpy(d, c, sizeof(d)); for (int i = 1, a, b; i < n; i++)scanf("%d%d", &a, &b), fa[b] = a; memset(vis, 0, sizeof(vis)); for (int i = 1; i < n; i++) { int p; double k = 0; for(int j=1;j<=n;j++) if (j != r && !vis[j] && c[j] > k) { k = c[j]; p = j; } int f = fa[p]; while (vis[f]) fa[p] = f = fa[f];//getfather nxt[la[f]] = p; la[f] = la[p]; num[f] += num[p]; tot[f] += tot[p]; c[f] = tot[f] / num[f]; vis[p] = 1; } int ans = 0; for (int i = 1; i <= n; i++) { ans += i * d[r]; r = nxt[r]; } printf("%d\n", ans); } int main() { while (scanf("%d%d", &n, &r) == 2 && n && r) color_a_tree(); return 0; }

 

转载于:https://www.cnblogs.com/lincold/p/10123568.html