[POJ2054]Color a Tree (并查集+贪心)

时间：2022-05-20 05:14:22

[POJ2054]Color a Tree (并查集+贪心)

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 = ; i <= n; i++)

    {

        scanf("%lf", &c[i]);

        nxt[i] = i; la[i] = i; num[i] = ; tot[i] = c[i];

    }

    memcpy(d, c, sizeof(d));

    for (int i = , a, b; i < n; i++)scanf("%d%d", &a, &b), fa[b] = a;

    memset(vis, , sizeof(vis));

    for (int i = ; i < n; i++)

    {

        int p;

        double k = ;

        for(int j=;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] = ;

    }

    int ans = ;

    for (int i = ; i <= n; i++)

    {

        ans += i * d[r];

        r = nxt[r];

    }

    printf("%d\n", ans);

}

int main()

{

    while (scanf("%d%d", &n, &r) ==  && n && r) color_a_tree();

    return ;

}

相关文章