hdu--6090--Rikka with Graph

太过爱你忘了你带给我的痛 2022-06-10 03:25 113阅读 0赞

# Rikka with Graph #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)  
Total Submission(s): 432    Accepted Submission(s): 272**

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

题意： 
给你n个点，你可以在这n个点之间任意连<=m条线，使∑ni=1∑nj=1dist(i,j).的值最小。

其中dist(i,j)表示如过i和j之间有通路，则dist(i,j)的值为i和j之间经过的边数。如a--->b---c

（前提是没有a--->c，如过有的话，就取 1 而不是 2 ，因为要使值最小)那么dist(a,c)等于2  
因为经过了两条边，如过a和b之间没有通路，那么dist(a,b)就等于n。

解题思路： 
很显然，这是一道找规律的题，根据m和n的关系进行分类讨论， 
1,   如过m>=n\*(n-1)/2;就说明图中任意的两个点之间都有通路，答案可以直接得出，为n\*(n-1); 
2,  如过n-1<=m<n\*(n-1)/2,就拿n\*(n-1)的情况一个边 一个边的进行拆除，每拆除一个边，答案就增加二， 
     拆除边的数量为n\*(n-1)/2)-m，答案要加上的值就为2\*（n\*(n-1)/2)-m）； 
3，如过m<n-1的话，这时就产生了孤立的点，因为连接n个点，至少需要n-1条边。这时就把连通的点和

孤立的点分开算，  
ps:设孤立的点的个数为q，连通的点的个数为p;

对于孤立的点：每个点之间的权重为n，这几个孤立的对答案的贡献为q\*(q-1)\*n;  
   对于连通的点：比较容易得出这几个连通的点，对答案的贡献为(p-1)\*(p-1)\*2;    
   最后再把孤立的点与非孤立的点进行连通，他们之间的权重都为n，对答案的贡献都为q\*p\*n，所以为2倍的q\*p\*n；

代码：

C++ Code

<table style="width:100%; font-family:'Consolas','Courier New'; font-size:12px; vertical-align:text-top; line-height:15px"> 
 <tbody> 
 <tr> 
 <td style="color:#008284; background-color:#e3e3e3; vertical-align:text-top"> 
 <div style="margin:7px; text-align:right; white-space:nowrap">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 
 </div> </td> 
 <td style="background-color:#008284; padding:1px"> 
 <div style="border:1px #008284 solid"></div> </td> 
 <td style="background-color:rgb(239,239,239); width:100%; vertical-align:text-top"> 
 <div style="margin:7px"> 
 #include&lt;bits/stdc++.h&gt; 
 
 using&nbsp; 
 namespace&nbsp;std; 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;t; 
 &nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d",&nbsp;&amp;t); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(t--) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 long&nbsp; 
 long&nbsp;n,&nbsp;m,&nbsp;p,&nbsp;q; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%lld%lld",&nbsp;&amp;n,&nbsp;&amp;m); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 long&nbsp; 
 long&nbsp;ans&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;flag&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(m&nbsp;&gt;&nbsp;n&nbsp;*&nbsp;(n&nbsp;-&nbsp; 
 1)&nbsp;/&nbsp; 
 2) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%lld\n",&nbsp;n&nbsp;*&nbsp;(n&nbsp;-&nbsp; 
 1)); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;flag&nbsp;=&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else&nbsp; 
 if(m&nbsp;&gt;=&nbsp;n&nbsp;-&nbsp; 
 1&nbsp;&amp;&amp;&nbsp;m&nbsp;&lt;=&nbsp;n&nbsp;*&nbsp;(n&nbsp;-&nbsp; 
 1)&nbsp;/&nbsp; 
 2) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans&nbsp;+=&nbsp;((n&nbsp;*&nbsp;(n&nbsp;-&nbsp; 
 1)&nbsp;/&nbsp; 
 2)&nbsp;-&nbsp;m)&nbsp;*&nbsp; 
 2&nbsp;+&nbsp;n&nbsp;*&nbsp;(n&nbsp;-&nbsp; 
 1); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p&nbsp;=&nbsp;m&nbsp;+&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;q&nbsp;=&nbsp;n&nbsp;-&nbsp;m&nbsp;-&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans&nbsp;+=&nbsp;q&nbsp;*&nbsp;p&nbsp;*&nbsp;n&nbsp;*&nbsp; 
 2&nbsp;+&nbsp;q&nbsp;*&nbsp;(q&nbsp;-&nbsp; 
 1)&nbsp;*&nbsp;n&nbsp;+&nbsp;(p&nbsp;-&nbsp; 
 1)&nbsp;*&nbsp;(p&nbsp;-&nbsp; 
 1)&nbsp;*&nbsp; 
 2; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(flag&nbsp;==&nbsp; 
 0) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%lld\n",&nbsp;ans); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 } 
 
 </div> </td> 
 </tr> 
 </tbody> 
</table>