【BFS】L2-007. 家庭房产

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <stack> #include <map> #include <queue> using namespace std; const int INF = 0x3f3f3f3f; const int N = 10010; const double esp = 1e-6; struct node { int num; int tao; int mian; }a[N]; struct asd { double avet; double avem; int minn; int num; }h[N]; bool cmp2(asd a,asd b) { if(a.avem != b.avem) return a.avem > b.avem; return a.minn < b.minn; } map<int,int> mp; vector<int> p[N]; int vis[N]; int k; void bfs(int x) { int minn = INF; int ansm = 0; int ansg = 0; int num = 0; queue<int> q; int now; q.push(x); vis[x] = 1; while(!q.empty()) { now = q.front(); q.pop(); minn = min(minn,a[now].num); ansm += a[now].mian; ansg += a[now].tao; num++; for(int i = 0; i < p[now].size(); i++) { if(!vis[p[now][i]]) { q.push(p[now][i]); vis[p[now][i]] = 1; } } } h[k].minn = minn; h[k].num = num; h[k].avem = ansm*1.0/num; h[k].avet = ansg*1.0/num; k++; } bool chu(int x) { if(x == -1) return false; if(mp[x] == 0) mp[x] = mp.size(); a[mp[x]].num = x; return true; } int main() { int n; cin >> n; mp.clear(); for(int i = 0; i < n; i++) { int x,b,c,ge; cin >> x >> b >> c >> ge; chu(x); x = mp[x]; if(chu(b)) { p[x].push_back(mp[b]); p[mp[b]].push_back(x); } if(chu(c)) { p[x].push_back(mp[c]); p[mp[c]].push_back(x); } while(ge--) { int child; cin >> child; if(chu(child)) { p[x].push_back(mp[child]); p[mp[child]].push_back(x); } } cin >> a[x].tao >> a[x].mian; } memset(vis,0,sizeof(vis)); k = 0; for(int i = 1; i <= mp.size(); i++) { if(!vis[i]) bfs(i); } sort(h,h+k,cmp2); printf("%d\n",k); for(int i = 0; i < k; i++) printf("d %d %.3lf %.3lf\n",h[i].minn,h[i].num,h[i].avet,h[i].avem); return 0; }