HDU6090 Rikka with Graph

系统管理员 2022-06-10 03:30 97阅读 0赞

Problem Description  
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 G with n nodes and m edges, we can define the distance between (i,j) (dist(i,j)) as the length of the shortest path between i and j. The length of a path is equal to the number of the edges on it. Specially, if there are no path between i and j, we make dist(i,j) equal to n.

Then, we can define the weight of the graph G (wG) as ∑ni=1∑nj=1dist(i,j).

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

Yuta wants to know the minimal value of wG.

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).

Input  
The first line contains a number 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).

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

Sample Input  
1  
4 5

Sample Output  
14

Source  
2017 Multi-University Training Contest - Team 5

题目大意：  
给你n个结点和m条边，设计一个无向图，使得点与点之间的权值最小。点与点之间的权值是这样定义的：对于i和j两个结点如果存在路，则其权值为经过边的条数，否则权值为n

题解：  
大家不妨试着打出一个表出来，就会发现其中的一些规律：当一某个中心结点增加边是是最佳的图，所以我们就可分3种情况讨论。  
第一个是这个图不连通，那我们可以把不连通与连通的部分分开来计算，未连通的部分有一个坑，要注意防止重复计算，因此大家可以把它当作一个等差数列计算总的未连通的路（权值为n）有几条（即：（n-1）*(n-k)/2）,之后加说连通图中权值为1的有几条（即（n-k-1））和权值为2的有几条（即：（n-k-1）*（n-k-2）/2）。最后记得每个式子 乘以2，因为是无向图  
如果边刚好是n-1条，则用第一个公式同样可以做，  
如果边数小于等于n\*(n-1)/2,则从n-1边开始，每增加一条边就减少2  
如果边数大于n\*(n-1)/2，则就是边数等于n\*(n-1)/2时的结果

AC代码：

#include<bits/stdc++.h>
    using  namespace std;
    
    int main(){
        int t;
        long long n,m;
        cin>>t;
        while(t--){
            cin>>n>>m;
            if(m<=n-1){
                long long k=(n-m-1);
                cout<<((n-1)+(n-k))*k*n+(n-k-1)*2+(n-k-1)*(n-k-2)*2<<endl;
            }else if(m>n-1&&m<n/2*(n-1)){
                cout<<(n-1)*2+(n-1)*(n-2)*2-(m-(n-1))*2<<endl;
            }else{
                cout<<n*(n-1)<<endl;
            }
        }
        return 0;
    }