 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
难道是传说中的精度问题?In Reply To:为啥我按这个方法wa了...用并查集查找连通分量，然后按照度平均分来着.... Posted by:z12y12l12 at 2007-09-06 14:54:25 > #include <stdio.h>
> #include <string.h>
>
> int n, m;
> int d[101];
> int x[101];
> int father[101];
> int sum[101];
> int num[101];
>
> int ancestor(int i){
> int stack[100];
> int top = 0;
> while(father[i] > 0){
> stack[top++] = i;
> i = father[i];
> }
> while(top-- > 0){
> father[stack[top]] = i;
> }
> return i;
> }
>
> int main(){
> int i;
> int t, o;
> int cs;
> scanf("%d", &cs);
> while(cs-- > 0){
> memset(d, 0, sizeof(d));
> memset(father, 0, sizeof(father));
> memset(sum, 0, sizeof(sum));
> memset(num, 0, sizeof(num));
> scanf("%d%d", &n, &m);
> for(i = 1; i <= n; i++){
> scanf("%d", &x[i]);
> }
> for(i = 0; i < m; i++){
> scanf("%d%d", &t, &o);
> d[t]++;
> d[o]++;
> if(ancestor(t) != ancestor(o)){
> father[ancestor(t)] = ancestor(o);
> }
> }
> for(i = 1; i <= n; i++){
> t = ancestor(i);
> num[t] += d[i];
> sum[t] += x[i];
> }
> for(i = 1; i <= n; i++){
> t = ancestor(i);
> if(d[i] > 0)
> printf("%.3lf\n", (double)sum[t] / num[t] * d[i]);
> else
> printf("%.3lf\n", (double)sum[t]);
> }
> printf("\n");
> }
> return 0;
> }
Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
