【POJ 2054】 Color a Tree

【题目链接】

http://poj.org/problem?id=2054

【算法】

贪心

【代码】

#include <algorithm>

#include <bitset>

#include <cctype>

#include <cerrno>

#include <clocale>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <limits>

#include <list>

#include <map>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <utility>

#include <vector>

#include <cwchar>

#include <cwctype>

#include <stack>

#include <limits.h>

using namespace std;

#define MAXN 1010

struct info

{

        double w,size;

} a[MAXN];

int i,n,r,ans,pos,u,v,j;

int fa[MAXN];

bool vis[MAXN];

double mx;

vector< int > son[MAXN];

int main()

{

        while (scanf("%d%d",&n,&r) && n && r)

        {

                ans = ;

                memset(vis,false,sizeof(vis));

                for (i = ; i <= n; i++) son[i].clear();

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

                {

                        scanf("%lf",&a[i].w);

                        ans += (int)a[i].w;

                        a[i].size = ;

                }

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

                {

                        scanf("%d%d",&u,&v);

                        fa[v] = u;

                        son[u].push_back(v);

                }

                vis[r] = true;

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

                {

                        mx = ;

                        for (j = ; j <= n; j++)

                        {

                                if (!vis[j] && double(a[j].w / a[j].size) > mx)

                                {

                                        mx = double(a[j].w / a[j].size);

                                        pos = j;

                                }

                        }

                        ans += a[fa[pos]].size * a[pos].w;

                        vis[pos] = true;

                        a[fa[pos]].w += a[pos].w;

                        a[fa[pos]].size += a[pos].size;

                        for (j = ; j < son[pos].size(); j++)

                        {

                                fa[son[pos][j]] = fa[pos];

                                son[fa[pos]].push_back(son[pos][j]);

                        }

                }

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

        }

        return ;

}