浙江财经大学
信息管理与工程学院

HDU 5922 Minimum’s Revenge

本文由 Ocrosoft 于 2016-10-06 18:51:31 发表

Minimum’s Revenge

Problem Description
There is a graph of n vertices which are indexed from 1 to n. For any pair of different vertices, the weight of the edge between them is the least common multipleof their indexes.
Mr. Frog is wondering about the total weight of the minimum spanning tree. Can you help him?
 

Input
The first line contains only one integer T (T≤100), which indicates the number of test cases.
For each test case, the first line contains only one integer n (2≤n≤109), indicating the number of vertices.
 

Output
For each test case, output one line “Case #x:y”,where x is the case number (starting from 1) and y is the total weight of the minimum spanning tree.
 

Sample Input
2
2
3
 

Sample Output
Case #1: 2
Case #2: 5
Hint
In the second sample, the graph contains 3 edges which are (1, 2, 2), (1, 3, 3) and (2, 3, 6). Thus the answer is 5. 

Solution
题意:有n个顶点,将这些顶点连起来(使连通),两个顶点相连的值是顶点序号的最小公倍数。要求这个连通的图的边权值和最小。
思路:一看还是个图论,后来瞎蒙一下,所有其他顶点都和顶点1相连,那么就是2+3+…+n。然后就没有然后了…

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define ms(a) memset(a,0,sizeof(a))
typedef long long LL;
const LL LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const int MAXN = 100000 + 10;
const int MOD = 100000;
const double eps = 1e-6;
int gcd(int a, int b)
{
	if (!b)return a;
	return gcd(b, a%b);
}
using namespace std;
//or2..or2..or2..or2..or2..//
int main()
{
	LL n;
	while (cin >> n)
	{
		for (LL i = 1; i <= n; i++)
		{
			LL t; cin >> t;
			printf("Case #%I64d: %I64d\n", i, (2 + t)*(t - 1) / 2);
		}
	}
	return 0;
}

 

欢迎转载,请保留出处与链接。Ocrosoft » HDU 5922 Minimum’s Revenge

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址