# 2017 ACM-ICPC 亚洲区（乌鲁木齐赛区）网络赛- A. Banana

• 题目来源：Banana
• 题目描述和输出： 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，i,j indicate that the i-th monkey favours the j-th type of banana.

In the each line of following MM lines, two positive integers j, k，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 or equal to 50.

Output Format

For each test case, output all the pairs x, y，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，x,y which owns a smaller xx 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.

1 6 4 1 1 1 2 2 1 2 3 3 3 4 1 1 1 1 3 2 2 3 3 样例输出

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

• 题目分析： 第i个猴子喜欢第j种水果，这种水果在第k个地方，将两个关系矩阵压在一起，利用不同的标记分开i,j和j,k，最后输出。 矩阵乘法求传递闭包也是一种思路，但是实现很麻烦.
• 完整代码：
```#include <bits/stdc++.h>
using namespace std;
const int N = 60;
int a[N][N], b[N][N];
int main()
{
//freopen("2.txt", "r", stdin);
int T;
int x, y, z;
scanf("%d", &T);
while (T--)
{
int n, m;
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
{
scanf("%d%d", &x, &y);
a[x][y] = 1;
}
for (int i = 0; i < m; i++)
{
scanf("%d%d", &y, &z);
if (!a[y][z])
a[y][z] = 2;
else
a[y][z] = 3;
}
for (int i = 0; i <= 50; i++)
for (int j = 0; j <= 50; j++)
for (int k = 0; k <= 50; k++)
{
if ((a[i][k] == 1 && a[k][j] == 2) || (a[i][k] == 1 && a[k][j] == 3) || (a[i][k] == 3 && a[k][j] == 2) || (a[i][k] == 3 && a[k][j] == 3))
b[i][j] = 1;
}
for (int i = 0; i <= 50; i++)
for (int j = 0; j <= 50; j++)
{
if (b[i][j])
printf("%d %d\n", i, j);
}
printf("\n");
}
return 0;

}```

0 条评论

• ### HDU 5536--Chip Factory(暴力)

Chip Factory Time Limit: 18000/9000 MS (Java/Others) Memory Limit: 262144/26...

• ### POJ 2007--Scrambled Polygon(计算凸包，点集顺序)

Scrambled Polygon Time Limit: 1000MS Memory Limit: 30000K Total Submiss...

• ### 【Codeforces】1213B - Bad Prices

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### hdu----（5045）Contest（数位dp）

Contest Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (J...

• ### Codeforces 626E Simple Skewness(暴力枚举+二分)

E. Simple Skewness time limit per test:3 seconds memory limit per test:256 megab...

• ### HDU 3032 Nim or not Nim?(Multi-Nim)

Problem Description Nim is a two-player mathematic game of strategy in which ...

• ### ZOJ 3705 Applications

Recently, the ACM/ICPC team of Marjar University decided to choose some new memb...

• ### AIM Tech Round 4 (Div. 2)(A，暴力，B，组合数，C，STL+排序)

A. Diversity time limit per test：1 second memory limit per test：256 megabytes in...

• ### PAT 甲级 1003Emergency(Dijkstra最短路)

1003. Emergency (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序...

### 活动推荐 