n villages want to establish some **bi-directional** roads to achieve interconnection.Building a road requires a certain cost. Specifically, building a bi-directional road between village. ). The construction of a bi-directional road will be completed jointly by the two villages connected by this road. However, the human resources that each village can provide are limited. Village. n villages reachable to each other via roads?
There are n n villages, numbered from 1 1 to n n. Initially, these n n villages are all isolated. Now, these n n villages want to establish some **bi-directional** roads to achieve interconnection. Building a road requires a certain cost. Specifically, building a bi-directional road between village i i and village j j costs (i^2+j^2) (i 2 +j 2 ). The construction of a bi-directional road will be completed jointly by the two villages connected by this road. However, the human resources that each village can provide are limited. Village i i can participate in the construction of at most d_i d i roads. In other words, there can be at most d_i d i roads that have village i i as one endpoint. What is the minimum cost to make all n n villages reachable to each other via roads?
标签： HBC252122母牛的俄罗斯轮盘赌 思维Interconnection题解
