OI

【并查集】家谱&字符串hash

并查集的第一题

////题目描述////

家谱
源程序名 GEN.???(PAS,C,CPP)

可执行文件名 GEN.EXE

输入文件名GEN.IN

输出文件名 GEN.OUT

时间限制 2S

现代的人对于本家族血统越来越感兴趣，现在给出充足的父子关系，请你编写程序找到某个人的最早的祖先。

输入
输入文件由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系由二行组成，用#name的形式描写一组父子关系中的父亲的名字，用+name的形式描写一组父子关系中的儿子的名字；接下来用?name的形式表示要求该人的最早的祖先；最后用单独的一个$表示文件结束。规定每个人的名字都有且只有6个字符，而且首字母大写，且没有任意两个人的名字相同。最多可能有1000组父子关系，总人数最多可能达到50000人，家谱中的记载不超过30代。

输出
按照输入文件的要求顺序，求出每一个要找祖先的人的祖先，格式：本人的名字+一个空格+祖先的名字+回车。

样例
GEN.IN
#George

+Rodney

#Arthur

+Gareth

+Walter

#Gareth

+Edward

?Edward

?Walter

?Rodney

?Arthur

$

GEN.OUT

Edward Arthur

Walter Arthur

Rodney George

Arthur Arthur

首先涉及到一个字符串处理，使用了一个超简陋的字符串hash：由题,名字由大小写字母组成，直接将字符串转换为52进制数

1
2
3
4
5
6
7
8
9
10
11
12
13
    int ord(char c){
        if(c>='A'&&c<='Z')return(c-'A');
        if(c>='a'&&c<='z')return(c-'a'+26);
        return -1; 
    }
    int hash(char s[]){
        int i,t=0;
        for(i=5;i>=0;i--)
          t+=base[5-i+1]*ord(s[i])%max;
        t%=max;
        return t;
    }
//ord()函数及模仿pascal里的那个(

剩下的就是模板式并查集操作了……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define max 50000
char s[10]={'\0'};
int father_num=0;
int base[10];
int h[max+5]={0};
struct node{
       char s[10];
       int father,rank;
};
struct node opt[max+5];
FILE *fin,*fout;
int ord(char c){
    if(c>='A'&&c<='Z')return(c-'A');
    if(c>='a'&&c<='z')return(c-'a'+26);
    return -1; 
}
int hash(char s[]){
    int i,t=0;
    for(i=5;i>=0;i--)
      t+=base[5-i+1]*ord(s[i])%max;
    t%=max;
    return t;
}
int find(char s[]){
    int t=h[hash(s)];
    int root=t,k,i;
    int path[max+5];
    k=0;
    while(root!=opt[root].father){
      k++;
      path[k]=root;
      root=opt[root].father;
    }
    for(i=1;i<=k-1;i++)
      opt[path[i]].father=root;
    return root;
}
void ask(char s[]){
     int t=h[hash(s)];
     int root=t,k,i;
     int path[max+5];
     fprintf(fout,"%s",s);
     fprintf(fout," ");
     k=0;
     while(root!=opt[root].father){
       k++;
       path[k]=root;
       root=opt[root].father;
     }
     for(i=1;i<=k-1;i++)opt[path[i]].father=root;
     fprintf(fout,"%s",opt[root].s);
     fprintf(fout,"\n");
}
int main(){
    fin=fopen("gen.in","r");
    fout=fopen("gen.out","w");
    int i;
    base[1]=1;
    for(i=2;i<6;i++)
      base[i]=base[i-1]*51%max;
    int n=0,t,pf,pr;                           //pf:position of father
                                               //pr:position of root
    char c;
    c=getc(fin);
    while(c!='?'){
      fscanf(fin,"%s",s); 
      n++;
      t=hash(s);
      if(c=='#'){                         //is father
        if(h[t]==0){
          h[t]=n;
          opt[n].father=n;
          opt[n].rank=1;
          strcpy(opt[n].s,s);
          pf=n;
        }
        else{
          n--;
          pr=find(s);
          pf=pr;
          //pf=h[t];
        }
      }
      else{                                  //is son
        if(h[t]==0){
          h[t]=n;
          opt[n].father=pf;
          opt[n].rank=opt[pf].rank+1;
          strcpy(opt[n].s,s);
        }
        else{
          n--;
          opt[h[t]].father=pf;
          opt[h[t]].rank=opt[pf].rank+1; 
        }
      }
      c=getc(fin);
      c=getc(fin);
    }
    while(c!='$'){                        //asking
      fscanf(fin,"%s",s); 
      ask(s);
      c=getc(fin);
      c=getc(fin);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}