Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 5342 --生物进化
5342: 生物进化
警告!
题目
状态
题解
题目描述
生物学家们发现了几种动物化石。他们将化石依次编号为 $1,2,3,\cdots,n-1,n$。 经过简单的分析,他们发现了一些规律:若动物 $A$ 是由动物 $B$ 经过若干次进化而成的,则称 $B$ 是 $A$ 的祖先,特别地,任意一种动物都是它自己的祖先(经过 $0$ 次进化);若动物 $A$ 是由动物 $B$ 经过一次进化而成的,则称 $B$ 是 $A$ 的直系祖先;$1$ 号动物无直系祖先,其它每种动物都有且仅有一个直系祖先;发现的动物化石中,$1$ 号的是它们共同的祖先;所有的动物都是从低级向高级进化。 为了进一步确定生物进化的过程,生物学家们经过复杂的分析和计算,得出这些化石两两间的“差异程度”。“差异程度”有如下性质:对于两个物种 $i,j$,它们的“差异程度”是一个非负整数,记为 $D_{i,j}$,$D_{i,i}=0, i=j$ 时,$D_{i,j}=D_{j,i}=0$;若 $i$ 是 $k$ 的祖先,$k$ 是 $j$ 的祖先则 $D_{i,j}=D_{i,k}+D_{k,j}$;若 $k$ 是 $i$ 和 $j$ 的所有公共祖先中最高级的,则 $D_{i,j}=D_{i,k}+D_{k,j}$。因此,利用“差异程度”,就可以确定生物进化的过程。 但是化石数量实在太多了,于是,生物学家们希望你能够帮助他们。
输入
第一行是一个整数 $n$,表示化石种类数。 接下来 $n$ 行,每行 $n$ 个整数,第 $i$ 行第 $j$ 个是$D_{i,j}$,表示 $i$ 和 $j$ 的“差异程度”。
输出
$n$ 行,第 $n$ 行是一个整数 ,表示 $n$ 号动物的直系祖先为 。
样例输入输出
输入#1
复制
4 0 1 4 7 1 0 5 8 4 5 0 3 7 8 3 0
输出#1
复制
1 1 3
提示
对于 $100\%$ 的数据,$1 \leq n \leq 1000, 0 \leq D_{i,j} \leq 100000$。
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
未评定
标签
生成树
点击显示
if ($pr_flag) { ?>
递交数
1
已通过
1
} ;?>
通过率
100%
时间限制
1 秒
内存限制
128 MB
来源
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和