B - Unrequited Love ZOJ - 3601【模拟】

Lokinli

发布于 2023-03-09 15:07:59

2070

发布于 2023-03-09 15:07:59

文章被收录于专栏：以终为始

B - Unrequited Love

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 coming q 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 -- n m q. Then each of the next n lines describes a boy, and each of the next m 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 last q 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 than 20. 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

&：n 个男生，m 个女生，告诉你这些人都有一些喜欢的人，可能是一个也可能是多个，然后 q 次询问，每次询问会给一些人，问这些人中是否存在一个人，没有人喜欢他，但是他喜欢其他所有的人（这群人中）。

#include <bits/stdc++.h>
#define long long ll
#define rep(i,a,b) for(int i = (a); i < (b); i ++)
#define per(i,a,b) for(int i = (a); i > (b); i --)
#define pb push_back
using namespace std;
const int maxn = 30050;
set<int>G[maxn];
map<string,int>mp;
string tmp[maxn];
bool used[maxn];
int main()
{
    ios::sync_with_stdio(false);
    int n,t,m,q,N,M,num;
    string u,v;
    cin >> t;
    while(t--)
    {
        cin >> n >> m >> q;
        mp.clear();
        rep(i,0,n+m+1)G[i].clear();
        N = 1;
        rep(i,0,n+m)
        {
            cin >> u;
            if(!mp[u])mp[u] = N++;
            cin >> num;
            rep(i,0,num)
            {
                cin >> v;
                if(!mp[v])mp[v] = N++;
                G[mp[u]].insert(mp[v]);
            }
        }
        bool ok = false;
        rep(i,0,q)
        {
            cin >> num;
            rep(j,0,num)
            {
                cin >> tmp[j];
                used[j] = 0;
            }
            rep(j,0,num)
            {
                if(used[j])continue; //如果标记过，代表有人喜欢，所以不用考虑
                ok = true;
                rep(k,0,num)
                {
                    if(j == k) continue; //代表是自己，continue
                    if(G[mp[tmp[j]]].count(mp[tmp[k]])) used[k] = true; //如果这个k被喜欢，就没必要搜索了
                    if(!G[mp[tmp[j]]].count(mp[tmp[k]])|| G[mp[tmp[k]]].count(mp[tmp[j]])) //如果j不喜欢k，j也不可以，或者被k喜欢
                    {
                        ok = false;
                        break;
                    }
                }
                if(ok)
                {
                    cout << "1" <<" "<<tmp[j] << endl;
                    break;
                }
            }
            if(!ok)cout << "0" <<endl;
        }
        cout <<endl;
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019-04-26，如有侵权请联系 cloudcommunity@tencent.com 删除

case