1009: 一带一路
时间限制: 1 Sec 内存限制: 128 MB
题目描述
一带一路是去去年习大大提出来的建设“新丝绸之路经济带”和“21世纪海上丝绸之路”的战略构想。其中就包括我们新疆乌鲁木齐，所以这也是对新疆来说是一个巨大的机遇。我们新疆要加强和周边国家的经济文化交流，就必然要和周边国家城市修许多路。现在假设有N座城市，每一个城市都有一个投资指标数，例如A城市和B城市的投资指标数分别为Ia和Ib，如果Ia或Ib或Ia-Ib的绝对值为素数或者为1，则A城市和B城市可以修路，否则不能。他们修路的花费为Ia，Ib，Ia-Ib的绝对值这三个数中的最小值，并且为素数或者1。现在已知所以城市之间的投资指标，假设他们直接原来没有任何路，要求你在其中修路联通这些城市（即任何两座城市之间都能直接或者间接的有路相通）。求修这些路最少花费总和。
输入
输入包含多组数据，第一行为测试数据T组（1<=T<=10）;以下每组数据第一行包含城市的个数N(1<N<=100)，接下来一行表示N个整数表示每个城市的投资指标数I（I为正整数，1<=I<=1000000）
输出
输出最小花费总和，如果无法使所以城市连通，则输出-1
样例输入
2
5
1 2 3 4 5
4
4 4 4 4
样例输出
Case 1: 4
Case 2: -1 题目链接：https://acm.xju.edu.cn/JudgeOnline/problem.php?id=1009 数据量1000000的素数，比较大，一个一个算肯定超时，所以我用了小红书上O（n）的素数筛选法。
然后最小生成树有两种求法，第一种是Prim算法，第二种是Kruskal算法。
时间复杂度都是O(|E|log|V|)。 第一种用邻接矩阵，第二种用邻接表。
这里数据量比较小，直接用Prim算法。 懒得自己打就抄个模板就好了。 两个模板O（n）的素数筛选和Prim求最小生成树。 代码：
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std; int a[]; int s[][]; //邻接矩阵 //O(n)的素数筛选，见小红书算法与实现
int ans[]; //按顺序记录素数
bool valid[]; // valid[i] == true 表示 i是素数
int tot = ; //素数的个数
void getPrime(int n){
memset(valid,true,sizeof(valid)); for(int i = ;i <= n; i++){
if(valid[i]){
tot++;ans[tot] = i;
}
for(int j = ;((j <= tot)&&(i*ans[j] <= n)); j++){
valid[i*ans[j]] = false;
if(i&ans[j] == ) break;
}
}
} int mincost[]; //记录从源点0到点i的最小花费
bool used[]; // 记录i点是否使用过 int prim(int n){
for(int i = ;i < n; i++){
mincost[i] = 2e9;
used[i] = false;
}
mincost[] = ;
int res = ;
while(true){
int v = -;
for(int u = ;u < n; u++){
if(!used[u] && (v == - || mincost[u] < mincost[v])) v = u;
}
if(v == -||mincost[v] == 2e9) break;
used[v] = true;
res += mincost[v];
for(int u = ;u < n; u++){
mincost[u] = min(mincost[u],s[v][u]);
}
}
//判断是否有点没有用过，即不能产生最小生成树
int flag = ;
for(int i = ;i < n; i++){
if(!used[i]){
flag = ;
break;
}
}
if(flag) return -;
if(res <= ) return -;
return res;
} int main() { //O(n)的素数筛选
getPrime();
int t,n;
cin >> t; int num = ; while(t--){
for(int i = ;i < ; i++){
for(int j = ;j < ; j++){
s[i][j] = 2e9;
}
}
cin >> n;
for(int i = ;i < n; i++){
cin >> a[i];
}
for(int i = ;i < n; i++){
for(int j = i+;j < n; j++){ //找到3个数中最小的素数
int p = abs(a[i]-a[j]);
int d[] = {p,a[i],a[j]};
sort(d,d+);
for(int k = ;k < ; k++){
if(valid[d[k]]){
//如果为素数则跳出，此时是最小的素数
s[i][j] = d[k];
s[j][i] = d[k];
break;
}
}
//没有素数，即不产生一条边
if(s[i][j] == ) s[i][j] = 2e9;
}
} cout << "Case " << ++num << ": ";
cout << prim(n) << endl;
} return ;
}