#include "testlib.h" #include #include #include using namespace std; struct DSU { vector p; DSU(int n): p(n+1) { for(int i = 0; i <= n; i++) p[i] = i; } int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); } void unite(int a, int b) { a = find(a); b = find(b); if (a != b) p[b] = a; } }; int main(int argc, char* argv[]) { registerGen(argc, argv, 1); // 1) Number of students int N = rnd.next(1, 10); // 2) Friend costs A_i int maxAi = rnd.next(1, 20); vector A(N+1); for (int i = 1; i <= N; i++) { A[i] = rnd.next(1, maxAi); } // 3) Build all possible undirected edges (including self-loops) int pairsCount = N * (N + 1) / 2; vector> allPairs; allPairs.reserve(pairsCount); for (int i = 1; i <= N; i++) { for (int j = i; j <= N; j++) { allPairs.emplace_back(i, j); } } // 4) Hyper-parameter to choose how many unique edges double mode = rnd.next(); int M_unique; if (mode < 0.3) { // skew to fewer edges M_unique = rnd.wnext(pairsCount + 1, -2); } else if (mode < 0.6) { // uniform M_unique = rnd.next(0, pairsCount); } else { // skew to more edges M_unique = rnd.wnext(pairsCount + 1, 2); } if (M_unique > pairsCount) M_unique = pairsCount; shuffle(allPairs.begin(), allPairs.end()); allPairs.resize(M_unique); // 5) Possibly add a few duplicate edges vector> edges = allPairs; int dupMax = M_unique > 0 ? min(M_unique/2, 2) : 0; int dupCnt = rnd.next(0, dupMax); for (int i = 0; i < dupCnt; i++) { edges.push_back(rnd.any(allPairs)); } int M = edges.size(); // 6) Compute minimum total cost needed DSU dsu(N); for (auto &e : edges) { dsu.unite(e.first, e.second); } const int INF = numeric_limits::max(); vector compMin(N+1, INF); for (int i = 1; i <= N; i++) { int r = dsu.find(i); compMin[r] = min(compMin[r], A[i]); } long long needed = 0; for (int i = 1; i <= N; i++) { if (dsu.find(i) == i) { needed += compMin[i]; } } // 7) Decide k: sometimes valid, sometimes too small int k; double pick = rnd.next(); if (needed > 1 && pick < 0.4) { // make it impossible k = rnd.next(1, (int)needed - 1); } else { // make it possible int extra = rnd.next(0, 20); k = (int)needed + extra; } // 8) Output println(N, M, k); // costs for (int i = 1; i <= N; i++) { printf("%d%c", A[i], i==N?'\n':' '); } // edges for (auto &e : edges) { println(e.first, e.second); } return 0; }

코드 #5463