Multi-University Training HDU - 6090

Multi-University Training HDU - 6090，题目大意：每两个点之间的边数代表这两个点的距离，求总和最小的距离总和。

官方题解：

解题思路：先画了四个点，然后一条边一条边的添加，发现都连在同一个点上的话，其他点都通过他到另一个点，长度才2，然后等到那个点与其他点都相连了之后，随意加边到未连的点上，不论加到那个点，发现通过一定的翻转，其实和其他点相连是一样的(即他们是等价的，都是使距离减一)然后就是考虑如何计算了，先考虑连边最多的a点，再考虑和a点相连的点，他们都是等价的，所以乘他们的个数，然后考虑孤立点，孤立点也是等价的，所以也乘他们的个数

AC代码：

#include
using namespace std;

typedef long long LL;
const int Maxn = 100000 + 5;

int gt[Maxn];

int main()
{
    int t;scanf("%d", &t);
    while (t--)
    {
        LL n, m,ans;
        scanf("%I64d%I64d", &n, &m);
        if (m <= n - 1)
        {
            int left = n - m - 1;//孤立点
            ans = m + left*n + (2 * m - 1 + left*n)*m + left*(n - 1)*n;
        }
        else if (m < n*(n - 1) / 2)
            ans = n - 1 + (2 * n - 3)*(n - 1) - (m - n + 1) * 2;
        else
            ans = (n - 1)*n;
        printf("%I64d\n", ans);     
    }
    return 0;
}