一眼望去……好麻烦的样子……
只会一一对应啊怎么破怎么破【好愁人啊、、、
然后,想想,是不是不要用map 做呢……看着对面的Empty大神,我默默放下了这种想法……
可是还是不会啊。。。Map同志的一对多【臣妾做不到啊啊啊啊……
好吧,百度一下…… 非人类们都说用set 的 multiset<int >
然后我应该就会了……
先是建立 map<int , multiset<int>>
,考虑到下面会经常出现这个东西, 就用typedef 定义了一下,嗯,随手定义成了 mp
然后写了一个方法,也是本题的核心算法: 每次查询, 输出对应的map 中的符合的元素数,然后删除另一个map中对应的数据。
然后基础的部分就是map的一般算法。
AC Memory : 12492 KB Time : 1359 MS
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <map> #include <set> #include <iterator> using namespace std; typedef map<int,multiset<int> > mp; void pop(mp &a,mp &b,int i) { printf("%d\n",a[i].size()); for(multiset<int>::iterator it = a[i].begin();it!=a[i].end();++it) { b[*it].erase(i); } a[i].clear(); } int main() { int N,M,x,y; scanf("%d%d",&N,&M); while(N!=0 &&M!= 0) { mp a; mp b; for(int i = 0;i<N;++i) { scanf("%d%d",&x,&y); a[x].insert(y); b[y].insert(x); } for(int i = 0;i<M;i++) { scanf("%d%d",&x,&y); if(x==0) { pop(a,b,y); } else { pop(b,a,y); } } cout<<endl; scanf("%d%d",&N,&M); } return 0; }