2017 ACM-ICPC 亚洲区（乌鲁木齐赛区）网络赛-A. 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, ji,j indicate that the ii-th monkey favours the j-th type of banana.
In the each line of following M lines, two positive integers j, kj,k indicate that the jj-th type of banana could be find in the kk-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, yx,y that the xx-the monkey can accept at least one type of bananas from the yy-th place.
These pairs should be outputted as ascending order. That is say that a pair of x, yx,y which owns a smaller xx should be output first.
If two pairs own the same xx, output the one who has a smaller yy 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
2017 ACM-ICPC 亚洲区（乌鲁木齐赛区）网络赛-第一题，读懂题目以后其实比较简单，算是签到题目吧。
题目意思说深林里面有一个公司，有一个张表格记录了两个数据，第一个记录了猴子喜欢吃哪种香蕉。
第二个记录的某一种类型的香蕉来源于哪个产地。
最后题目问的是，猴子可以从哪个产地得到自己喜欢吃的香蕉，输出所有可能。输出的时候有顺序，按照从小到大输出，第一个相同时，按照第二个从小到大输出。
开始题面给的测试数据都错了。
题解：数据范围比较小，我就用的是比较暴力的方法。
每次遍历猴子和它喜欢吃的香蕉的种类，然后在遍历香蕉的产地，然后把猴子和产地记录下来。放到结构体里面排序，输出的时候遇到相同的就跳过。
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, ji,j indicate that the ii-th monkey favours the j-th type of banana.
In the each line of following M lines, two positive integers j, kj,k indicate that the jj-th type of banana could be find in the kk-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, yx,y that the xx-the monkey can accept at least one type of bananas from the yy-th place.
These pairs should be outputted as ascending order. That is say that a pair of x, yx,y which owns a smaller xx should be output first.
If two pairs own the same xx, output the one who has a smaller yy 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
2017 ACM-ICPC 亚洲区（乌鲁木齐赛区）网络赛-第一题，读懂题目以后其实比较简单，算是签到题目吧。
题目意思说深林里面有一个公司，有一个张表格记录了两个数据，第一个记录了猴子喜欢吃哪种香蕉。
第二个记录的某一种类型的香蕉来源于哪个产地。
最后题目问的是，猴子可以从哪个产地得到自己喜欢吃的香蕉，输出所有可能。输出的时候有顺序，按照从小到大输出，第一个相同时，按照第二个从小到大输出。
开始题面给的测试数据都错了。
题解：数据范围比较小，我就用的是比较暴力的方法。
每次遍历猴子和它喜欢吃的香蕉的种类，然后在遍历香蕉的产地，然后把猴子和产地记录下来。放到结构体里面排序，输出的时候遇到相同的就跳过。
详情看代码
这一套题目里面好多图论题，Orz，还是懂的太少了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<vector>
using namespace std;
vector<int> list1[100];
vector<int> list2[100];
int cnt;
int t,n,m;
struct node
{
int from,to;
}edge[2555];
void init()
{
cnt=0;
memset(edge,0,sizeof edge);
for(int i=0;i<=50;i++)
{
list1[i].clear();
list2[i].clear();
}
}
bool cmp(struct node a,struct node b)//排序函数
{
if(a.from==b.from)
return a.to<b.to;
return a.from<b.from;
}
void solve()
{
int i,j,k;
for(i=1;i<=50;i++)//遍历猴子
{
int sz=list1[i].size();
for(j=0;j<sz;j++)//遍历香蕉
{
int s=list2[ list1[i][j] ].size();
for(k=0;k<s;k++)//遍历产地
{
edge[cnt].from=i;//把猴子和产地联系起来，加入结构体
edge[cnt].to=list2[list1[i][j]][k];
//printf("from=%d to=%d\n",edge[cnt].from,edge[cnt].to);
cnt++;
}
}
}
}
int main()
{
int i,j,k;
int a,b;
while(scanf("%d",&t)!=EOF)
{
while(t--)
{
scanf("%d%d",&n,&m);
init();
for(i=1;i<=n;i++)
{
scanf("%d%d",&a,&b);
list1[a].push_back(b);
}
for(i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
list2[a].push_back(b);
}
solve();
sort(edge,edge+cnt,cmp);
for(i=0;i<cnt;i++)
{
if(edge[i].from==edge[i+1].from&&edge[i].to==edge[i+1].to)
continue;//遇到相同的数据跳过
printf("%d %d\n",edge[i].from,edge[i].to);
}
printf("\n");
}
}
return 0;
}
查看12道真题和解析
