【POJ 2054】 Color a Tree
2024-08-28 06:13:13
【题目链接】
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 ; }
最新文章
- 自己封装的一个原生JS拖动方法。
- CNUOJ 0486 800401反质数
- Mac OS 下 mysql 找不到 mysql.sock 的问题
- 当你还在纠结于ORM的性能时,我已经远远的把你抛在脑后
- MatLab 组件大全
- 前端新手分析 AJAX执行顺序,数据走向
- samba 常见问题
- lintcode:Palindrome Partitioning 分割回文串
- Jabber Software:Jabber-NET、agsXMPP与Wilefire[转]
- iOS最新上线流程+续费 2015-7-20更新
- C# 字符串驻留池
- Linux下编译boost库和qt和ImageMagick
- Hadoop学习之Hadoop集群搭建
- 跨域访问 REST API
- Spark:导入数据到oracle
- 15个优秀的开源项目,让你轻松应对Android开发
- Android开发学习笔记-GridView的动态显示
- JavaScript 包管理工具npm 和yarn 对比
- input 控件监听回车确认按钮。
- Spring 事物传播特性
热门文章
- jquery的delegate()方法
- TWaver3D特效系列之环境映射
- 散列(hash)
- [bzoj1833][ZJOI2010][count] (数位dp)
- Vue如何tab切换高亮最简易方法
- type=";application/javascript";
- pace.js – 网页自动加载进度条插件
- How to put username &;password in MongoDB(Security&;Authentication)?(配置用户认证在MongoDB)
- Win32编程API 基础篇 -- 2.一个简单的窗口 根据英文教程翻译
- PageUtil ,简单的分页工具