Detail of message

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

为啥我按这个方法wa了...用并查集查找连通分量，然后按照度平均分来着....

Posted by z12y12l12 at 2007-09-06 14:54:25 on Problem 1926
In Reply To:按下面说的对每个连通分量按度的百分比进行量的分配做确实可以AC，不过不知道应该怎么证明？ Posted by:rovingcloud at 2007-05-18 13:41:03

#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:

偶也是.. (1498) bjtuacmer200701 2007-09-06 14:57:20
难道是传说中的精度问题? (1498) bjtuacmer200701 2007-09-06 14:57:47
- 不太可能吧....double啊...而且仅要求保留3位的，又或者..该方法本身就有问题? (0) z12y12l12 2007-09-06 15:00:49
  - 方法绝对没有问题.很容易就能发现的出来 (0) bjtuacmer200701 2007-09-06 15:04:44
    - 过了. (0) bjtuacmer200701 2007-09-06 15:10:25
    - 什么意思.. (0) z12y12l12 2007-09-06 15:12:37
    - 我明白，我也知道方法肯定是对的，也不是很难想...不过我的程序究竟哪个地方wa了..... (0) z12y12l12 2007-09-06 15:13:55
      - 我用的是DFS求连通分支. (0) bjtuacmer200701 2007-09-06 15:19:28
        刚才是我粗心把变量写错了 (0) bjtuacmer200701 2007-09-06 15:19:50
        教训啊....输入是real number....正确的读题是AC的一半啊 (0) z12y12l12 2007-09-06 15:24:53
        Re:教训啊....输入是real number....正确的读题是AC的一半啊 (21) songxuehui 2009-10-19 10:49:37

Post your reply here:

User ID:
Password:
Title:

Content:

> #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;
> }

Home Page Go Back To top