POJ1988、并查集、路径压缩

追尾巴

最近在做POJ上面的题，做题的时候使用的是C语言。今天把其中的一道题用AS400里的RPG语言重新写了一遍。
题目地址如下：
http://acm.pku.edu.cn/JudgeOnline/problem?id=1988

首先是考虑输入。我将输入改为使用文件来输入了。建立的物理文件如下：

                R INPUT
                  LINE          14A         COLHDG('LINE')

里面的保存的内容为：

Position to line  . . . . .           
....+....1....                        
LINE                                 
6                                    
M 1 6                                 
C 1                                   
M 2 4                                 
M 2 6                                 
C 3                                   
C 4                                   
********  End of data  ********

      

然后是写了一个RPG程序：

1.      FPF1988    IF   E             DISK
   
2.      D A               S              5S 0 DIM(30000)
   
3.      D B               S              5S 0 DIM(30000)
   
4.      D C               S              5S 0 DIM(30000)
   
5.      D W               S              5S 0 DIM(30000)
   
6.      D N               S              5S 0
   
7.      D I               S              5S 0
   
8.      D J               S              5S 0
   
9.      D X               S              5S 0
   
10.      D Y               S              5S 0
    
11.      D T               S              5S 0
    
12.      D CO              S              1A
    
13.      D P               S              5S 0
    
14.      D STR             S             15A
    
15.      C                   EXSR      SR_MAIN
    
16.      C                   EXSR      SR_END
    
17.      C     SR_MAIN       BEGSR
    
18.      C                   EXSR      SR_INIT
    
19.      C                   READ      INPUT
    
20.      C                   EVAL      T=%DEC(LINE:5:0)
    
21.      C                   DO        T
    
22.      C                   READ      INPUT
    
23.      C                   EVAL      CO=%SUBST(LINE:1:1)
    
24.      C                   IF        CO='M'
    
25.      C     ' '           SCAN      LINE:3        P
    
26.      C                   EVAL      I=%DEC(%SUBST(LINE:3:P-3):5:0)
    
27.      C                   EVAL      J=%DEC(%SUBST(LINE:P+1:5):5:0)
    
28.      C                   EXSR      SR_MOVE
    
29.      C                   ELSEIF    CO='C'
    
30.      C                   EVAL      I=%DEC(%SUBST(LINE:3:5):5:0)
    
31.      C                   EXSR      SR_COUNT
    
32.      C                   ENDIF
    
33.      C                   ENDDO
    
34.      C                   EXSR      SR_END
    
35.      C                   ENDSR
    
36.      C     SR_END        BEGSR
    
37.      C                   RETURN
    
38.      C                   ENDSR
    
39.      C     SR_INIT       BEGSR
    
40.      C                   EVAL      I=1
    
41.      C                   DO        30000
    
42.      C                   EVAL      A(I)=I
    
43.      C                   EVAL      B(I)=0
    
44.      C                   EVAL      C(I)=1
    
45.      C                   EVAL      I=I+1
    
46.      C                   ENDDO
    
47.      C                   ENDSR
    
48.      C     SR_MOVE       BEGSR
    
49.      C                   EVAL      X=I
    
50.      C                   EVAL      Y=J
    
51.      C                   EVAL      N=1
    
52.      C                   DOW       X<>A(X)
    
53.      C                   EVAL      W(N)=X
    
54.      C                   EVAL      N=N+1
    
55.      C                   EVAL      X=A(X)
    
56.      C                   ENDDO
    
57.      C                   DOW       Y<>A(Y)
    
58.      C                   EVAL      Y=A(Y)
    
59.      C                   ENDDO
    
60.      C                   IF        X<>Y
    
61.      C                   EVAL      A(X)=Y
    
62.      C                   EVAL      B(X)=C(Y)
    
63.      C                   EVAL      C(Y)=C(Y)+C(X)
    
64.      C                   EVAL      N=N-1
    
65.      C                   DOW       N>0
    
66.      C                   EVAL      B(W(N))=B(W(N))+B(A(W(N)))
    
67.      C                   EVAL      A(W(N))=Y
    
68.      C                   EVAL      N=N-1
    
69.      C                   ENDDO
    
70.      C                   ENDIF
    
71.      C                   ENDSR
    
72.      C     SR_COUNT      BEGSR
    
73.      C                   EVAL      X=I
    
74.      C                   EVAL      Y=I
    
75.      C                   EVAL      N=1
    
76.      C                   DOW       A(X)<>A(A(X))
    
77.      C                   EVAL      W(N)=X
    
78.      C                   EVAL      N=N+1
    
79.      C                   EVAL      X=A(X)
    
80.      C                   ENDDO
    
81.      C                   EVAL      N=N-1
    
82.      C                   DOW       N>0
    
83.      C                   EVAL      B(W(N))=B(W(N))+B(A(W(N)))
    
84.      C                   EVAL      A(W(N))=A(N)
    
85.      C                   EVAL      N=N-1
    
86.      C                   ENDDO
    
87.      C     B(Y)          DSPLY
    
88.      C                   ENDSR

复制代码

运行的结果如下：

DSPLY      1            
DSPLY      0            
DSPLY      2            
                        
Press Enter to continue.

程序使用了并查集的路径压缩，在大量操作的时候非常节省时间。

[ 本帖最后由 追尾巴 于 2009-9-21 14:36 编辑 ]

追尾巴

后来把输出也放到一个文件里面了
并且测试了一下耗时
结果大概是：
DSPLY  use time: .017856 sec

居然是17毫秒！
这道题如果用RPG来提交一定会超时的

[ 本帖最后由 追尾巴 于 2009-9-21 14:19 编辑 ]

追尾巴

用C语言测试的结果是：
1
0
2
use time: 0.000607 sec
Press any key to continue

耗时居然是29：1的关系

zyzng

以下问题:
1.C语言程序也用FILE?可以贴出C的程序?
2.试下块读取.

RPG/ILE RPG速度是比C快,这是测试过的

追尾巴

原帖由 zyzng 于 2009-9-21 21:40 发表
以下问题:
1.C语言程序也用FILE?可以贴出C的程序?
2.试下块读取.

RPG/ILE RPG速度是比C快,这是测试过的

C程序是在windows下用VC写的。
运行的时候使用了参数“<1.txt >2.txt”来定位两个文件。1.txt是输入的文件，2.txt是用来输出的文件。

#include <stdio.h> int a[30001]; int b[30001]; int c[30001]; int w[30001]; int n; void move(int i,int j){     int x=i,y=j;     n=0;     while(x!=a[x]){         w[n]=x;         n++;         x=a[x];     }     while(y!=a[y]) y=a[y];     if(x==y) return;     a[x]=y;     b[x]=c[y];     c[y]+=c[x];     for(i=n-1;i>=0;i--){         b[w[i]]+=b[a[w[i]]];         a[w[i]]=y;     } } void count(int i){     int x=i,y=i;     n=0;     while(a[x]!=a[a[x]]){         w[n]=x;         n++;         x=a[x];     }     for(i=n-1;i>=0;i--){         b[w[i]]+=b[a[w[i]]];         a[w[i]]=a[x];     }     printf("%dn",b[y]); } int main(){     int i,n;     char o;     int x,y;     for(i=1;i<=30000;i++){         a[i]=i;b[i]=0;c[i]=1;     }     scanf("%d",&n);     while(n--){         scanf("n%c",&o);         if(o=='M'){             scanf("%d %d",&x,&y);             move(x,y);         }else if(o=='C'){             scanf("%d",&x);             count(x);         }     }     return 0; }