本文主要是介绍2017多校5 1006 Rikka with Graph，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=6090
很简单的一道题，因为自己不够贪心所以还是细节漏了点。
给出n个点m条边，去把n个点连起来，边不够的话也可以连，只不过权值变成了n，正常的边权值等于该2点间的边的数量，求从map[1][1]到map[n][n]的和最小。
因为m条边不一定全用完，那么肯定2个点最多只会连1条边，因为数据特别大，所以肯定是有公式的，既然有公式，那么图就一定很好算，很容易就能想到图是一个从1个点想四周去延展的网状图，那么就很简单了，从中心点到四周都是1，从四周到其他四周点，都是2，这是正好是最小生成树边数的情况，如果边不够，就把多余点连到中心点上，权值为n，如果m>n-1那么多一条边，答案就减2，可以打表发现，也可以自己理解(因为本来相连是2的，现在变成1了，一来一回就减少了2)。
如果m>=(n-1)*n/2那么答案就是一张边全为1的完全图。
重点！因为权值为n的边是可以任意连的，是没有数量限制的，所以如果边不够的话，多余的点不应该是只用权值为n的边连到中心点的，应该是往其余每个点上都连一条权值为n的边。。。这就是为什么我不够贪心的原因，真的是太蠢了我。。。
#include<iostream>
using namespace std;
long long n,m;
int main(){long long t;cin>>t;while(t--){cin>>n>>m;if(n==1){cout<<"0"<<endl;continue;}if(m>=(n-1)*n/2){long long ans=n*(n-1);cout<<ans<<endl;}else if(m>n-1){long long ans=2*n*(n-1);ans=ans-2*m;cout<<ans<<endl;}else if(m<=n-1){long long y=n-m-1;long long ans1=y*n*(n-1)+(n-y)*y*n;long long ans2=m+m+2*m*(m-1);long long ans=ans1+ans2;cout<<ans<<endl;}}return 0;
}这篇关于2017多校5 1006 Rikka with Graph的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
