2014
03-06

Marriage Match

You may know the funny problem “The Stable Marriage Problem”. Now let’s find a new match algorithm.
Firstly the women and men stand in a line separately and each woman will choose the man she likes.
Then it’s your task to make a match for these people. You should choose m women and m men from the initial queues. Let them stand in a line separately by initial order. If the woman stands in the ith place do not like the man stands in the ith place, the match is unacceptable. To increase the possibility of the match, the women can accept the men their friends like. Please find out the maximal m.

There are several test cases.
Each test case starts with two integer p and q in a line means the number of women and the number of men.(0 < p , q <= 100000)
Then a line with p numbers follows means the queue of women. (The id ranges from 1 to p)
Then a line with q numbers follows means the queue of men. (The id ranges from 1 to q)
Then a line with p numbers which means the man the ith woman likes.
Then a line with an integer t, means the number of friendships between women.(0 < t < 100000)
Then t lines follow. Each line contains two numbers a and b means a and b are friends.(a!=b, 1 <= a, b <= p)
You may support the friendship can transmit. If a and b are friends and c and b are friends, then a and c are friends. Notice every woman will have no more than five friends.

There are several test cases.
Each test case starts with two integer p and q in a line means the number of women and the number of men.(0 < p , q <= 100000)
Then a line with p numbers follows means the queue of women. (The id ranges from 1 to p)
Then a line with q numbers follows means the queue of men. (The id ranges from 1 to q)
Then a line with p numbers which means the man the ith woman likes.
Then a line with an integer t, means the number of friendships between women.(0 < t < 100000)
Then t lines follow. Each line contains two numbers a and b means a and b are friends.(a!=b, 1 <= a, b <= p)
You may support the friendship can transmit. If a and b are friends and c and b are friends, then a and c are friends. Notice every woman will have no more than five friends.

4 4
1 3 2 4
1 4 2 3
2 3 1 2
2
1 2
3 4

2

1. #include <cstdio>
#include <cstring>

const int MAXSIZE=256;
//char store[MAXSIZE];
char str1[MAXSIZE];
/*
void init(char *store) {
int i;
store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
for(i=’F';i<=’Z';++i) store =i-5;
}
*/
int main() {
//freopen("input.txt","r",stdin);
//init(store);
char *p;
while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
if(p=fgets(str1,MAXSIZE,stdin)) {
for(;*p;++p) {
//*p=store[*p]
if(*p<’A’ || *p>’Z') continue;
if(*p>’E') *p=*p-5;
else *p=*p+21;
}
printf("%s",str1);
}
fgets(str1,MAXSIZE,stdin);
}
return 0;
}

2. 如果两个序列的最后字符不匹配（即X [M-1]！= Y [N-1]）
L（X [0 .. M-1]，Y [0 .. N-1]）= MAX（L（X [0 .. M-2]，Y [0 .. N-1]），L（X [0 .. M-1]，Y [0 .. N-1]）
这里写错了吧。