题目大意:
要求构造一张图,并让该图满足以下条件:
- 有 \(n\) 个点,\(m\) 条边。
- 每条边的边权范围是 \([1,10^9]\)。
- 图中从 \(1\) 到 \(n\) 的最短路径长度是个质数。
- 最小生成树的边权和为质数。
- 没有重边和自环。
题目分析:
先用质数筛筛一遍,然后因为与生成树相关,所以不难想到先构造一颗树,然后在树上添加边权为 \(+\infty\) 的边。又因为要满足最短路径的长度为质数,所以方便起见,我们可以先构造一朵菊花,然后再在其上面加边即可。
时间复杂度 \(O(n+m)\)。
代码实现:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define TIME_LIMIT (time_t)2e3
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#define inf (int)1e9
#define MAX_SIZE (int)2e6
bitset<MAX_SIZE>nf;
int primes[MAX_SIZE];
void primeshai(int num) {
for (int i = 2; i < num; i++) {
if (!nf[i])
primes[++primes[0]] = i;
for (int j = 1; j <= primes[0] && primes[j]*i <= num; j++) {
nf[i * primes[j]] = 1;
if (i % primes[j] == 0)
break;
}
}
}
signed main() {
ios::sync_with_stdio(false);
#ifdef LOCAL
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
time_t cs = clock();
#endif
//========================================
primeshai(MAX_SIZE);
int m, n;
cin >> n >> m;
int nowsum = (n - 2) * 2;
int lastw = primes[1];
for (int i = 1; i <= primes[0] && primes[i] + nowsum < MAX_SIZE; i++) {
if (!nf[nowsum + primes[i]]) {
nowsum += primes[i];
lastw = primes[i];
break;
}
}
cout << 2 << ' ' << nowsum << endl;
cout << 1 << ' ' << 2 << ' ' << lastw << endl;
for (int i = 2; i < n; i++)
cout << 1 << ' ' << i + 1 << ' ' << 2 << endl;
int cnt = 0;
m -= n - 1;
while (cnt < m) {
for (int i = 2; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
cout << i << ' ' << j << ' ' << inf << endl;
cnt++;
if (cnt >= m)
break;
}
if (cnt >= m)
break;
}
}
//========================================
#ifdef LOCAL
fclose(stdin);
fclose(stdout);
time_t ce = clock();
cerr << "Used Time: " << ce - cs << " ms." << endl;
if (TIME_LIMIT < ce - cs)
cerr << "Warning!! Time exceeded limit!!" << endl;
#endif
return 0;
}
标签:int,题解,质数,CF916C,primes,边权,define
From: https://www.cnblogs.com/larry76/p/17127350.html