1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
| #include <bits/stdc++.h> using namespace std;
const int N = 10000;
int n; int d[N], cnt[N], s[N], p[N]; int mp[N]; struct Node{ int id, t; double c, s; };
int find(int x) { if(x != p[x]) p[x] = find(p[x]); return p[x]; }
bool cmp(Node &x, Node &y) { if(x.s == y.s) return x.id < y.id; return x.s > y.s; }
void merge(int a, int b) { if(d[a] == -1) d[a] = 1; if(b != -1 && d[b] == -1) d[b] = 1; if(b == -1) return ; int fa = find(a), fb = find(b); if(fa == fb) return ; d[fb] += d[fa]; cnt[fb] += cnt[fa]; s[fb] += s[fa]; mp[fb] = min(mp[fb], mp[fa]); p[fa] = p[fb]; }
int main() { cin >> n; for(int i = 1; i < 10000; i ++ ) mp[i] = i, p[i] = i; memset(d, -1, sizeof d); for(int i = 0; i < n; i ++ ) { int id, f, m, k; cin >> id >> f >> m >> k; merge(id, f); merge(id, m); for(int j = 0; j < k; j ++ ) { int x; cin >> x; merge(id, x); } int x, y; cin >> x >> y; int fid = find(id); cnt[fid] += x; s[fid] += y; }
vector<Node> v; for(int i = 0; i < N; i ++ ) if(d[i] != -1 && i == find(i)) { v.push_back({mp[i], d[i], cnt[i] * 1.0 / d[i], s[i] * 1.0 / d[i]}); } sort(v.begin(), v.end(), cmp); cout << v.size() << endl; for(int i = 0; i < v.size(); i ++ ) printf("%04d %d %.3lf %.3lf\n", v[i].id, v[i].t, v[i].c, v[i].s); return 0; }
|