4 条题解
-
1
[CCO2021] Travelling Merchant
#include <bits/stdc++.h> using namespace std; int n, m; struct Edge { int a, b, r, p, id; }; bool vis[212345]; // 标记每个id的边还在不在 bool operator<(const Edge &x, const Edge &y) { return x.r < y.r; } priority_queue<Edge> pq; Edge e[212345]; vector<Edge> ee[212345]; vector<Edge> eee[212345]; int inD[212345], outD[212345]; queue<int> q; int ans[212345]; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) ans[i] = 1000000001; for (int i = 1; i <= m; i++) { cin >> e[i].a >> e[i].b >> e[i].r >> e[i].p; e[i].id = i; // 用来标记每条边还在不在 vis[i] = true; inD[e[i].b]++; outD[e[i].a]++; ee[e[i].a].push_back((Edge){e[i].a, e[i].b, e[i].r, e[i].p, e[i].id}); // 反图 eee[e[i].b].push_back((Edge){e[i].b, e[i].a, e[i].r, e[i].p, e[i].id}); } // 处理出度为0的 for (int i = 1; i <= n; i++) if (outD[i] == 0) q.push(i); while (!q.empty()) { int u = q.front(); q.pop(); ans[u] = -1; for (int i = 0; i < eee[u].size(); i++) { int v = eee[u][i].b; int id = eee[u][i].id; vis[id] = false; outD[v]--; if (outD[v] == 0) q.push(v); } } // 剩下的边丢进优先队列 pq for (int i = 1; i <= m; i++) { if (vis[i] == true) pq.push(e[i]); } // 从大往小处理pq中的边 while (!pq.empty()) { Edge now = pq.top(); pq.pop(); int u = now.a; int v = now.b; int r = now.r; int p = now.p; int id = now.id; if (vis[id] == false) continue; ans[u] = min(ans[u], now.r); vis[id] = false; // cout << u << "," << ans[u] << "\n"; outD[u]--; if (outD[u] == 0) { // u的答案确定了 q.push(u); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < eee[u].size(); i++) { int v = eee[u][i].b; int r = eee[u][i].r; int p = eee[u][i].p; int id = eee[u][i].id; if (vis[id]==false) continue; vis[id] = false; ans[v] = min(ans[v], max(r, ans[u] - p)); // cout << v << ":" << ans[v] << "\n"; outD[v]--; if (outD[v] == 0) q.push(v); } } } } for (int i = 1; i <= n; i++) cout << ans[i] << " "; return 0; } -
1
33DAI LV 5 (1/1) @ 2023-1-28 9:03:22
排水系统
#include <bits/stdc++.h> #define int long long using namespace std; struct PQ { __int128 p, q; // p/q }; __int128 gcd(__int128 a, __int128 b) { if (b == 0) return a; return gcd(b, a % b); } __int128 lcm(__int128 a, __int128 b) { return a / gcd(a, b) * b; } PQ operator+(const PQ &a, const PQ &b) { __int128 nq = lcm(a.q, b.q); __int128 np = a.p * (b.q / gcd(a.q, b.q)) + (a.q / gcd(a.q, b.q)) * b.p; PQ res = (PQ){np, nq}; __int128 d = gcd(res.p, res.q); res.p /= d; res.q /= d; return res; } void fixed(PQ &a) { __int128 d = gcd(a.p, a.q); a.p /= d; a.q /= d; } void write(__int128 x) { if (x >= 10) write(x / 10); cout << (int)(x % 10); } int n, m; int inD[112345]; int outD[112345]; vector<int> e[112345]; PQ ans[112345]; queue<int> q; signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int u = 1; u <= n; u++) { cin >> outD[u]; for (int j = 1; j <= outD[u]; j++) { int v; cin >> v; e[u].push_back(v); inD[v]++; } ans[u] = (PQ){0, 1}; } for (int i = 1; i <= m; i++) ans[i] = (PQ){1, 1}; for (int i = 1; i <= n; i++) if (inD[i] == 0) q.push(i); while (!q.empty()) { int u = q.front(); q.pop(); int num = e[u].size(); if (num == 0) continue; PQ temp = ans[u]; temp.q *= num; fixed(temp); for (int i = 0; i < e[u].size(); i++) { int v = e[u][i]; ans[v] = ans[v] + temp; inD[v]--; if (inD[v] == 0) q.push(v); } } for (int i = 1; i <= n; i++) if (outD[i] == 0) { write(ans[i].p); cout << " "; write(ans[i].q); cout << "\n"; } return 0; } -
1
[USACO08DEC]Trick or Treat on the Farm G
#include <bits/stdc++.h> using namespace std; bool flag; int n; int nxt[112345]; int dis[112345]; //答案 int tot; int dfn[112345]; int qst, qlen; //当前环起点、环长度 void dfs(int now, int st) { int fa = nxt[now]; //走到了走过的点 if (dfn[fa] != 0) { //当前链找到了环 if (dfn[fa] >= st) { qst = dfn[fa]; qlen = dfn[now] - dfn[fa] + 1; dis[now] = qlen; } else dis[now] = dis[fa] + 1; return; } else { dfn[fa] = ++tot; dfs(fa, st); if (qst != -1 && dfn[now] >= qst) dis[now] = qlen; else dis[now] = dis[fa] + 1; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) cin >> nxt[i]; for (int i = 1; i <= n; i++) if (dis[i] == 0) { dfn[i] = ++tot; qst = -1; dfs(i, tot); } for (int i = 1; i <= n; i++) cout << dis[i] << "\n"; return 0; } -
0
拯救小云公主
#include <bits/stdc++.h> using namespace std; int n, U, D, L, R; double row, line; double dis[3005][3005]; double x[3005], y[3005]; int fa[3015]; int findFa(int x) { if (fa[x] == x) return x; return fa[x] = findFa(fa[x]); } bool check(double r) { for (int i = 1; i <= n + 4; i++) fa[i] = i; // 与四条边 for (int i = 1; i <= n; i++) { if (x[i] - 1 <= r) fa[findFa(D)] = findFa(i); if (row - x[i] <= r) fa[findFa(U)] = findFa(i); if (y[i] - 1 <= r) fa[findFa(L)] = findFa(i); if (line - y[i] <= r) fa[findFa(R)] = findFa(i); } // BOSS 之间 for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { if (dis[i][j] <= (r * 2)) fa[findFa(i)] = findFa(j); } } // 返回结果 if ((findFa(U) == findFa(D)) || (findFa(L) == findFa(R)) || (findFa(L) == findFa(D)) || (findFa(U) == findFa(R))) return false; return true; } int main() { cin >> n >> row >> line; for (int i = 1; i <= n; i++) cin >> x[i] >> y[i]; U = n + 1, D = n + 2, L = n + 3, R = n + 4; // 预处理距离，避免tle for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { dis[i][j] = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])); } } double l = 0; double r = 1e6; while ((r - l) > 1e-6) { double mid = (l + r) / 2; if (check(mid)) l = mid; else r = mid; } cout << fixed << setprecision(2) << l << "\n"; return 0; }
- 1