具有最小广义Randic指标的双圈图的任务书.docx

具有最小广义Randic指标的双圈图的任务书
任务描述：
给定一个无向双圈图G，其中每个圈的大小均不小于3。请你设计一个算法，在保持G的边数不变的情况下，重新排列G的节点，使得G具有最小的广义Randic指标。广义Randic指标被定义为G中所有顶点Degree之和的平方与边数e的比值，即
R(G)=(sum(deg(v))^2)/e
其中v是G的任意一个顶点，deg(v)是v的Degree，e是G中的边数。
输入描述：
输入数据的第一行包含一个整数n，表示图G的节点数。
接下来n行，每行包含一个正整数，表示该节点所在的圈的大小。
输出描述：
输出一个长度为n的排列P，表示节点新的编号。例如，输出P=3142表示原来的节点1现在被重编号为3，节点2被重编号为1，节点3被重编号为4，节点4被重编号为2。同时输出G在排列P下的最小广义Randic指标Rmin。
样例输入：
6
3
3
4
5
4
5
样例输出：
216345
1.0769