2017 ACM-ICPC 亞洲區-banana

Discussion

Bananas are the favoured food of monkeys. 

In the forest, there is a Banana Company that provides bananas from different places. 

The company has two lists. 

The first list records the types of bananas preferred by different monkeys, and the 

second one records the types of bananas from different places. 

Now, the supplier wants to know, whether a monkey can accept at least one type of 

bananas from a place. 

Remenber that, there could be more than one types of bananas from a place, and there 

also could be more than one types of bananas of a monkey’s preference.

Input Format

The first line contains an integer T, indicating that there are T test cases. 

For each test case, the first line contains two integers N and M, representing the 

length of the first and the second lists respectively. 

In the each line of following N lines, two positive integers i, j indicate that the i-th 

monkey favours the j-th type of banana. 

In the each line of following M lines, two positive integers j, k indicate that the j-th 

type of banana could be find in the k-th place. 

All integers of the input are less than 50.

Output Format

For each test case, output all the pairs x, y that the x-the monkey can accept at least 

one type of bananas from the y-th place. 

These pairs should be outputted as ascending order. That is say that a pair of x, y 

which owns a smaller x should be output first. 

If two pairs own the same x, output the one who has a smaller y first. 

And there should be an empty line after each test case.

Sample Input

1 

6 4 

1 1 

1 2 

2 1 

2 3 

3 3 

4 1 

1 1 

1 3 

2 2 

3 3

Sample Output

1 1 

1 2 

1 3 

2 1 

2 2 

2 3 

3 3 

4 1 

4 3

題意：

輸入n和m，n行每行表示第i隻猴子喜歡第j種香蕉，m行每行表示第i種香蕉來自第j個地區； 問哪些猴子在哪些地區有喜歡的香蕉，按猴子序号（若同則按地區）升序輸出。

思路：

通過觀察，可把每對資料當作一個二進制關系，由n行部分和m行部分的二進制關系通過關系複合（離散數學）得到結果。這裡可通過 vector 和 map 的實作。

code：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int maxn = 55;
vector<int >nm[maxn];
int map[maxn][maxn];

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n, m, moky, bana, pls;
        for(int i=0;i<=50;i++)
            nm[i].clear();
        memset(map,0,sizeof(map));
        scanf("%d %d",&n, &m);
        for(int i = 0; i < n; i ++)
        {
            scanf("%d %d",&moky, &bana);
            nm[bana].push_back(moky);
        }
        for(int i = 0; i < m; i ++)
        {
            scanf("%d %d",&bana, &pls);
            for(unsigned int j = 0; j < nm[bana].size(); j ++)
                map[nm[bana][j]][pls] = 1;
        }
        for(int i = 1; i <= 50; i ++)
        {
            for(int j = 1; j <= 50; j ++)
                if(map[i][j])
                    printf("%d %d\n",i,j);
        }
        printf("\n");
    }
}