HDU 6090 17多校5 Rikka with Graph（思维简单题）

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

Input

The first line contains a number

Output

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

Sample Input

4 5

Sample Output

分成三种情况考虑

1.m大大的有，超过了n*(n-1)/2的情况，n*(n-1)/2说明每个点之间都有连线，那就是最少的情况n*(n-1)

2.m可以把所有点连在一起。这样的话随便推算几个就可以发现规律了。

3.m不够，然后就把连在一起和不连在一起的分开算，具体看代码注释。

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<queue>
 6 #include<cmath>
 7 #include<string>
 8 #include<map>
 9 #include<vector>
10 using namespace std;
11 
12 long long calc(long long n,long long m)
13 {
14     return 2*(n-1)*(n-1)-(m-n+1)*2;
15 }
16 
17 int main()
18 {
19     long long T,n,m,ans;
20     scanf("%d",&T);
21     while(T--)
22     {
23         scanf("%lld%lld",&n,&m);
24         if(m>=n*(n-1)/2)
25             ans=n*(n-1);
26         else if(m<n-1)
27             ans=calc(1+m,m)+(n-1-m)*(m+1)*2*n/*和连通的内部点连*/+(n-1-m)*(n-2-m)*n/*孤立的点之间*/;
28         else
29             ans=calc(n,m);
30         printf("%lld
",ans);
31     }
32     return 0;
33 }

HDU 6090 17多校5 Rikka with Graph（思维简单题）

相关推荐