81 lines
2.0 KiB
C++
81 lines
2.0 KiB
C++
|
|
|
|
#include "testlib.h"
|
|
|
|
#include <map>
|
|
#include <thread>
|
|
#include <vector>
|
|
|
|
using namespace std;
|
|
|
|
using ll = unsigned long long;
|
|
using pll = pair<ll, ll>;
|
|
|
|
const double eps = 1e-3;
|
|
|
|
struct EdgeData {
|
|
ll s, e;
|
|
double len;
|
|
};
|
|
|
|
void generate_edges(int thread_id, unsigned int seed, ll n, ll count,
|
|
vector<EdgeData> &output) {
|
|
random_t thread_rnd;
|
|
thread_rnd.setSeed(seed);
|
|
|
|
output.reserve(count);
|
|
|
|
for (ll i = 0; i < count; ++i) {
|
|
ll s = thread_rnd.next(1uLL, n);
|
|
ll e = thread_rnd.next(1uLL, n);
|
|
double len = thread_rnd.next(eps, 1.0 / eps);
|
|
output.push_back({s, e, len});
|
|
}
|
|
}
|
|
|
|
int main(int argc, char *argv[]) {
|
|
registerGen(argc, argv, 1);
|
|
|
|
ll n = opt<ll>("N");
|
|
double pm = opt<double>("pm");
|
|
|
|
ensuref(0 <= pm && pm <= 1, "pm must be in [0, 1]: %lf", pm);
|
|
ll m = n * (n - 1) * pm;
|
|
|
|
unsigned int n_threads = thread::hardware_concurrency();
|
|
if (n_threads == 0) n_threads = 2;
|
|
|
|
vector<unsigned int> seeds(n_threads);
|
|
for (unsigned int i = 0; i < n_threads; ++i) {
|
|
seeds[i] = rnd.next();
|
|
}
|
|
|
|
vector<thread> threads;
|
|
vector<vector<EdgeData>> thread_outputs(n_threads);
|
|
ll edges_per_thread = (m + n_threads - 1) / n_threads;
|
|
|
|
for (unsigned int i = 0; i < n_threads; ++i) {
|
|
threads.emplace_back(generate_edges, i, seeds[i], n, edges_per_thread,
|
|
ref(thread_outputs[i]));
|
|
}
|
|
|
|
map<pll, double> edges;
|
|
for (unsigned int i = 0; i < n_threads; ++i) {
|
|
threads[i].join();
|
|
|
|
for (const auto &data : thread_outputs[i]) {
|
|
if (edges.size() >= m) break;
|
|
if (data.s == data.e) continue;
|
|
if (edges.count({data.s, data.e})) continue;
|
|
edges[{data.s, data.e}] = data.len;
|
|
}
|
|
}
|
|
|
|
vector<pair<pll, double>> E;
|
|
for (auto [p, l] : edges) E.push_back({p, l});
|
|
shuffle(E.begin(), E.end());
|
|
|
|
println(n, m);
|
|
for (auto [p, l] : E) println(p.first, p.second, l);
|
|
}
|