There are n single boys and m single girls. Each of them may love none, one or several of other people unrequitedly and one-sidedly. For the comingq days, each night some of them will come together to hold a single party. In the party, if someone loves all the others, but is not loved by anyone, then he/she is called king/queen of unrequited love.
Input
There are multiple test cases. The first line of the input is an integer T ≈ 50 indicating the number of test cases.
Each test case starts with three positive integers no more than 30000 --nmq. Then each of the nextn lines describes a boy, and each of the nextm lines describes a girl. Each line consists of the name, the number of unrequitedly loved people, and the list of these people's names. Each of the lastq lines describes a single party. It consists of the number of people who attend this party and their names. All people have different names whose lengths are no more than20. But there are no restrictions that all of them are heterosexuals.
Output
For each query, print the number of kings/queens of unrequited love, followed by their names in lexicographical order, separated by a space. Print an empty line after each test case. See sample for more details.
Sample Input
2 2 1 4 BoyA 1 GirlC BoyB 1 GirlC GirlC 1 BoyA 2 BoyA BoyB 2 BoyA GirlC 2 BoyB GirlC 3 BoyA BoyB GirlC 2 2 2 H 2 O S He 0 O 1 H S 1 H 3 H O S 4 H He O S
Sample Output
0 0 1 BoyB 0 0 0
题目大意：给定一些关系，对于每个人（男孩或女孩），列出他所喜欢的人（允许同性恋），对于每次询问（聚会），求这样一种人：他喜欢所有人，但所有人都不喜欢他
分析：简单分析可知，这种人假如存在，最多只有一个。因为假设有2个这样的人，他们彼此就与题意矛盾。故可以枚举这个人，如何快速枚举？
对于一次聚会，先把第一个人假设为这种人，遍历其后的人，与当前这个人判断关系，若发现这个人不可能是这种人，则把当前遍历的更新为这种人。
扫一遍后，再判断这个人是否真的是，只要和他前面所有的人判断一下即可
#include<cstdio> #include<string> #include<set> #include<map> using namespace std; const int N=30005; map<string,int> M; map<string,int>::iterator it; set< pair<int,int> > S; string name[N]; int tol,party[N]; char na[22]; int hash(char *s){ //关键的一段函数，许多注意点 it=M.find(s); if(it!=M.end())return it->second; else { name[++tol]=s; return M[s]=tol; } } void Cin(int x){ int i,k,u,v; for(i=0;i<x;i++){ scanf("%s%d",na,&k); u=hash(na); while(k--){ scanf("%s",na); v=hash(na); S.insert(make_pair(u,v)); } } } int main(){ int T,n,m,q,i,k,ans; scanf("%d",&T); while(T--){ scanf("%d%d%d",&n,&m,&q); M.clear(),S.clear(),tol=0; Cin(n),Cin(m); while(q--){ scanf("%d%s",&k,na); ans=party[0]=M[na]; int p=0; for(i=1;i<k;i++){ scanf("%s",na),party[i]=M[na]; if(S.find(make_pair(ans,party[i]))==S.end()||S.find(make_pair(party[i],ans))!=S.end()){ //查找核心 ans=party[i],p=i; } } for(i=0;i<p;i++){ if(S.find(make_pair(ans,party[i]))==S.end()||S.find(make_pair(party[i],ans))!=S.end())break; } if(i!=p)puts("0"); else printf("1 %s ",name[ans].c_str()); //输出注意点 } puts(""); } return 0; }
name[]数组的输出：不能直接写成 printf("1 %s ",name[ans])，会出错，需要在后面加上“.c_str()”；
map<string,int>类型的容器，前面的string下标也可以用char类型的字符数组表示；
find（map和set都是可以用的）找不到就是==*.end(),找到就是!=*.end();
make_pair的用法，以及 map<string,int>::iterator it; 中it->second的用法
map清空也用clear；
传入函数中的字符数组用了“*”，并且后面没有“[]”；
摘自：http://blog.csdn.net/libing923/article/details/8902193
#include <iostream> #include<cstdio> #include<set> #include<map> using namespace std; map<string,int> mp; set< pair<int,int> > s; string name[30005]; int n,m,p,l; int party[30005]; int num(char *ch) { map<string,int>::iterator it; it=mp.find(ch); if (it!=mp.end()) return mp[ch]; else { name[++l]=ch; mp[ch]=l; return l; } } void read(int n) { char ch[26],str[26]; for(int i=1;i<=n;i++) { int k; scanf("%s%d",&ch,&k); int u=num(ch); for(;k>0;k--) { scanf("%s",&str); int v=num(str); s.insert(make_pair(u,v)); } } return; } int main() { int t; while(~scanf("%d",&t)) { for(;t>0;t--) { scanf("%d%d%d",&n,&m,&p); l=0; mp.clear(); s.clear(); read(n); read(m); for(int i=1;i<=p;i++) { int k; char ch[26]; scanf("%d",&k); for(int j=1;j<=k;j++) { scanf("%s",&ch); party[j]=mp[ch]; } bool flag; for(int j=1;j<=k;j++) { flag=1; for(int z=1;z<=k;z++) { if (j==z) continue; if (s.find(make_pair(party[j],party[z]))==s.end()) {flag=0;break;} if (s.find(make_pair(party[z],party[j]))!=s.end()) {flag=0;break;} } if (flag) {printf("1 %s ",name[party[j]].c_str());break;} } if (!flag) printf("0 "); } printf(" "); } } return 0; }
上面是自己写的，在上一个程序的借鉴上。