CUC-SUMMER-9-E

E - Rikka with Graph

HDU - 6090

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

For an undirected graph GG with nn nodes and mm edges, we can define the distance between (i,j)(i,j) (dist(i,j)dist(i,j)) as the length of the shortest path between ii and jj. The length of a path is equal to the number of the edges on it. Specially, if there are no path between ii and jj, we make dist(i,j)dist(i,j) equal to nn.

Then, we can define the weight of the graph GG (wGwG) as ∑ni=1∑nj=1dist(i,j)∑i=1n∑j=1ndist(i,j).

Now, Yuta has nn nodes, and he wants to choose no more than mm pairs of nodes (i,j)(i≠j)(i,j)(i≠j) and then link edges between each pair. In this way, he can get an undirected graph GG with nn nodes and no more than mm edges.

Yuta wants to know the minimal value of wGwG.

It is too difficult for Rikka. Can you help her?

In the sample, Yuta can choose (1,2),(1,4),(2,4),(2,3),(3,4)(1,2),(1,4),(2,4),(2,3),(3,4).

Input
The first line contains a number t(1≤t≤10)t(1≤t≤10), the number of the testcases.

For each testcase, the first line contains two numbers n,m(1≤n≤106,1≤m≤1012)n,m(1≤n≤106,1≤m≤1012).

Output
For each testcase, print a single line with a single number -- the answer.

Sample Input
1
4 5
Sample Output
14

题意：给你n个结点，m条边，连接成一个图，如果两个结点连通，那么距离为这两个结点之间的边的数量，如果不连通，距离为n，求所有节点与其他结点距离之和

解法：分情况讨论，m>=n(n-1)/2，n(n-1)/2m>=n-1，m<n-1

代码：

#include<iostream>
using namespace std;
int main()
{
    long long num,n,m;
    cin>>num;
    while(num--){
        cin>>n>>m;
        if(m>=(n-1)*n/2)
            cout<<n*(n-1)<<endl;
        else if(m>=n-1)
            cout<<2*n*(n-1)-2*m<<endl;
        else
            cout<<(2*(m-1)+1+(n-m-1)*n)*m+m+n*(n-m-1)+n*(n-1)*(n-m-1)<<endl;
    }
    return 0;
}