【题目链接】
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 = 0; memset(vis,false,sizeof(vis)); for (i = 1; i <= n; i++) son[i].clear(); for (i = 1; i <= n; i++) { scanf("%lf",&a[i].w); ans += (int)a[i].w; a[i].size = 1; } for (i = 1; i < n; i++) { scanf("%d%d",&u,&v); fa[v] = u; son[u].push_back(v); } vis[r] = true; for (i = 1; i < n; i++) { mx = 0; for (j = 1; 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 = 0; j < son[pos].size(); j++) { fa[son[pos][j]] = fa[pos]; son[fa[pos]].push_back(son[pos][j]); } } printf("%d ",ans); } return 0; }