OI

【网络流&字符串hash】拯救亚特兰蒂斯

////题目描述////
Bug魔王派出了N种怪物来入侵亚特兰蒂斯，聪明的亚特兰蒂斯国王Cubic预先得知了Bug魔王的阴谋，并了解到每种怪物都对应一种剑术和一种法术，这种怪物可以被对应的剑术打败也可以被对应的法术打败。不同的怪物可能对应不同的剑术和法术，而一种剑术或法术可以击败多种怪物。只要Cubic得到某怪物的信息，他就可以知道对应的剑术和法术，不会只知其一。
令国王感到欣慰的是亚特兰蒂斯最优秀的剑术师Xixi和最优秀的法术师Haha决定挺身而出，保卫国家。但问题是他们并不会这些特定的剑术和法术，必须抓紧时间学习。由于学习新剑术或新法术需要闭关，为防止Bug魔王偷袭，必须留下一个负责看守，因此两人不能同时学习。学习一种剑术或一种法术的时间都是1。现在的问题是他们到底需要学习那些剑术和法术，才能在最短的时间内拥有打败所有怪物的能力呢？
聪明的Cubic国王也发愁了，于是他决定聘请更聪明的你为亚特兰蒂斯的顶级技术顾问（相当于副科级），来帮他解决这个问题，全靠你了。
输入格式：输入有多组数据。对于每组数据：
第1行是3个整数 P（1<=P<=10000），N（0<=N<=500）和M（0<=M<=500），分别表示怪物、剑术和法术的种数。接下来P行，每行一个字符串，分别表示P种怪物的名字。
再接下来N+M行，表示一种剑术或法术的信息。前N行是剑术，后M行是法术。对于每一行，首先是一个字符串，表示剑术或法术的名字；然后是一个非负整数K(K<=P),表示这种剑术或法术可以击败的怪物种数；然后就是K个字符串，表示K种怪物的名字。这些怪物都在上面的P种怪物之内。
所有的字符串都只由字母和连字符（-）组成,长度不超过15。两个字符串以空格隔开。所有字符串都不相同。
最后1行有3个-1，表示输入结束。
输出格式：对于每组数据，输出一个整数，表示要拥有打败所有怪物的能力所需要的最少时间。如果无法打败所有的怪物，输出“Poor Atlantis!”。
Savior.in
5 3 2
ant
rocking
kinfkong
savior
magicpig
AlongNineSword 2 ant kinfkong
HuaShanSword 2 rocking savior
TaijiSword 1 magicpig
Wind_walk 3 ant rocking magicpig
Blade-storm 2 kinfkong savior
-1 -1 -1

Savior.out

2

一开始想的是建两幅图，分别是剑和怪，法术和怪的匹配，然后再跑两遍最大流，至少要全部覆盖，然后找两个之中最小的输出。
然而怪是1~10000个，节点数就非常大了。
因此引入概念：最小覆盖点集。我们可以将剑术放一边，法术放另一边，两边有共同的怪即为边，求最少的点，使得所有的边都覆盖。而最小覆盖点集等于最大匹配，只需求一边最大匹配即可。
然而，此题还涉及一个字符串hash。需要把怪，剑，法的名称转化为一定范围内的数值进行操作。由于怪物数据较大，冲突的情况很多。因此考虑怪物使用不用的hash算法。虽然十分暴力的挨个尝试了素数，又用了300多mb内存，才终于过了最后两个点。
只能算80分了 

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<memory.h>

typedef unsigned long long ull;
int p,n,m; 
const int MAXN=6908;
//const int MAXM=2005;
int g[MAXN][MAXN],y[MAXN],link[MAXN];
int monlist[10005]={0},
    swolist[MAXN]={0},
    maglist[MAXN]={0};
struct monster{
    int magic[501];
    int sword[501];
    int pm,ps;
};
struct monster mon[38834]={0};

int find(int sw){
    int i,ma;
    for(i=1;i<=m;i++){
        ma=maglist[i];
        if(g[sw][ma]&&!y[ma]){
            y[ma]=1;
            if(link[ma]==0||find(link[ma])){
                link[ma]=sw;
                return 1;
            }
        }
    }
        
    return 0;
}

//string hash

ull base=131;
ull mod=6907;
ull hashs(char s[])
{
    int len=strlen(s);
    ull ans=0;
    for (int i=0;i<len;i++)
        ans=(ans*base+(ull)s[i])%mod;
    return ans;
}

ull monmod=38833;
ull monhashs(char s[])
{
    int len=strlen(s);
    ull ans=0;
    for (int i=0;i<len;i++)
        ans=(ans*base+(ull)s[i])%monmod;
    return ans;
}

int main(){
    FILE *fin,*fout;
    int i,j,k,t2,nowmo,nowsw,nowma,endflag,ans;
    char t[20];
    fin=fopen("savior.in","r");
    fout=fopen("savior.out","w");
    while(1){
        fscanf(fin,"%d%d%d",&p,&n,&m);
        if(p==-1)break;
        for(i=1;i<=p;i++){
            fscanf(fin,"%s",t);
            nowmo=monhashs(t);
            monlist[i]=nowmo;
        }//monster
        
        for(i=1;i<=p;i++){
            nowmo=monlist[i];
            mon[nowmo].ps=0;
            mon[nowmo].pm=0;
        }
        
        for(i=1;i<=n;i++){
            fscanf(fin,"%s",t);
            nowsw=hashs(t);
            swolist[i]=nowsw;
            fscanf(fin,"%d",&t2);
            for(j=1;j<=t2;j++){
                fscanf(fin,"%s",t);
                nowmo=monhashs(t);
                mon[nowmo].sword[mon[nowmo].ps]=nowsw;
                mon[nowmo].ps++;
            }
        }//sword
        
        for(i=1;i<=m;i++){
            fscanf(fin,"%s",t);
            nowma=hashs(t);
            maglist[i]=nowma;
            fscanf(fin,"%d",&t2);
            for(j=1;j<=t2;j++){
                fscanf(fin,"%s",t);
                nowmo=monhashs(t);
                mon[nowmo].magic[mon[nowmo].pm]=nowma;
                mon[nowmo].pm++;
            }
        }//magic
        
        //build graph
        endflag=0;
        int fmon=0;
        memset(g,0,sizeof(g));
        memset(link,0,sizeof(link));
        for(i=1;i<=p;i++){
            fmon=0;
            nowmo=monlist[i];
            for(j=0;j<mon[nowmo].ps;j++)
                for(k=0;k<mon[nowmo].pm;k++){
                    g[mon[nowmo].sword[j]][mon[nowmo].magic[k]]=1;
                    fmon=1;
                }
            if(fmon)endflag++;
        }
        
        if(endflag<p){
            fprintf(fout,"Poor Atlantis!\n");
            continue;
        }
        
        ans=0;
        
        for(i=1;i<=n;i++){
            memset(y,0,sizeof(y));
            if(find(swolist[i]))ans++;
        }
    
        fprintf(fout,"%d\n",ans);
    }
    
    fclose(fin);
    fclose(fout);
    return 0;
}

5.29更新
感谢FLX菊苣提点，更新了C++版本，使用了STL的map，效率惊人……%%%%%

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
#include<iostream>
#include<cstdio>
#include<string.h>
#include<memory.h>
#include<map>
using namespace std;
int p,n,m; 
const int MAXN=2005;
//const int MAXM=2005;
int g[MAXN][MAXN],y[MAXN],link[MAXN];
struct monster{
    int magic[501];
    int sword[501];
    int pm,ps;
};
struct monster mon[10005]={0};

int find(int sw){
    int i,ma;
    for(i=1;i<=m;i++){
        ma=i*2+1;
        if(g[sw][ma]&&!y[ma]){
            y[ma]=1;
            if(link[ma]==0||find(link[ma])){
                link[ma]=sw;
                return 1;
            }
        }
    }
        
    return 0;
}

map<string,int> strmon,strswo,strmag;

int main(){
    int i,j,k,t2,nowmo,nowsw,nowma,endflag,ans;
    char t[20];
    while(1){
        scanf("%d%d%d",&p,&n,&m);
        if(p==-1)break;
        for(i=1;i<=p;i++){
            scanf("%s",t);
            strmon[t]=i;
        }//monster
        
        for(i=1;i<=p;i++){
            mon[i].ps=0;
            mon[i].pm=0;
        }
        
        for(i=1;i<=n;i++){
            scanf("%s",t);
            strswo[t]=i*2;
            scanf("%d",&t2);
            for(j=1;j<=t2;j++){
                scanf("%s",t);
                nowmo=strmon[t];
                mon[nowmo].sword[mon[nowmo].ps]=i*2;
                mon[nowmo].ps++;
            }
        }//sword
        
        for(i=1;i<=m;i++){
            scanf("%s",t);
            strmag[t]=i*2+1;
            scanf("%d",&t2);
            for(j=1;j<=t2;j++){
                scanf("%s",t);
                nowmo=strmon[t];
                mon[nowmo].magic[mon[nowmo].pm]=i*2+1;
                mon[nowmo].pm++;
            }
        }//magic
        
        //build graph
        endflag=0;
        int fmon=0;
        memset(g,0,sizeof(g));
        memset(link,0,sizeof(link));
        for(i=1;i<=p;i++){
            fmon=0;
            for(j=0;j<mon[i].ps;j++)
                for(k=0;k<mon[i].pm;k++){
                    g[mon[i].sword[j]][mon[i].magic[k]]=1;
                    fmon=1;
                }
            if(fmon)endflag++;
        }
        
        if(endflag<p){
            printf("Poor Atlantis!\n");
            continue;
        }
        
        ans=0;
        
        for(i=1;i<=n;i++){
            memset(y,0,sizeof(y));
            if(find(i*2))ans++;
        }
    
        printf("%d\n",ans);
    }
    return 0;
}