#include <cstdio> #define N 101 int f[N]; double p[N];//记录顶点污染指数 int con[N]; //记录连通数 int rank[N]; int total[N];//记录该集合总的连通数量 int Find(int x) { if(x != f[x]) { f[x] = Find(f[x]); } return f[x]; } void connect(int x, int y) { x = Find(x); y = Find(y); if(x == y) return; if(rank[x] > rank [y]) { f[y] = x; p[x] = p[y] + p[x]; total[x] = total[x] + total[y]; } else { f[x] = y; if(rank[x] == rank[y]) rank[y]++; p[y] = p[x] + p[y]; total[y] = total[x] + total[y]; } } int main() { int t, n, m; int x, y; scanf("%d", &t); while(t) { scanf("%d %d", &n, &m); for(int i = 1; i <= n ; i++) { scanf("%lf", &p[i]); con[i] = 0; rank[i] = 0; f[i] = i; total[i] = 0; } for(int i = 1; i <= m; i++) { scanf("%d %d", &x, &y); con[x]++; con[y]++; total[Find(x)]++; total[Find(y)]++; connect(x, y); } for(int i = 1; i <= n; i++) { x = Find(i); if(con[i] == 0) printf("%.3f\n",p[i]); else printf("%.3f\n",p[x] * con[i] / total[x]); } printf("\n"); t--; } return 0; } |
Double click to view unformatted code.