Two familiar concepts in object oriented programming are the is-a and has-a relationships. Given two classes A and B, we say that A is-a B if A is a subclass of B; we say A has-a B if one of the fields of A is of type B. For example, we could imagine an object-oriented language (call it ICPC++) with code like that in Figure E.1E.1E.1, where the class DayDayDay is-a TimeTimeTime, the class AppointmentAppointmentAppointment is both a DateBookDateBookDateBook and a ReminderReminderReminder, and class AppointmentAppointmentAppointment has-a DayDayDay.

These two relationships are transitive. For example if A is-a B and B is-a C then it follows that A is-a C. This holds as well if we change all the is-a's in the last sentence to has-a's. It also works with combinations of is-a's and has-a's: in the example above, AppointmentAppointmentAppointment has-a TimeTimeTime, since it has-a DayDayDay and DayDayDay is-a TimeTimeTime. Similarly, if class DateBookDateBookDateBook has-a YearYearYear then AppointmentAppointmentAppointment has-a YearYearYear, since AppointmentAppointmentAppointment is-a DateBookDateBookDateBook.

In this problem you will be given a set of is-a and has-a relationships and a set of queries of the form AAA is/has-a BBB. You must determine if each query is true or false.

\\[20pt]Input\normalsize \textbf{Input}Input

Input starts with two integers nnn and mmm, (1≤n,m≤10000)(1≤n,m≤10000)(1≤n,m≤10000), where nnn specifies the number of given is-a and has-a relationships and mmm specifies the number of queries. The next nnn lines each contain one given relationship in the form c1  r  c2c_1\;r\;c_2c1​rc2​ where c1c_1c1​ and c2c_2c2​ are single-word class names, and rrr is either the string "is-a" or "has-a". Following this are mmm queries, one per line, using the same format. There will be at most 500500500 distinct class names in the n+mn+mn+m lines, and all class names in the last mmm lines will appear at least once in the initial nnn lines. All is-a and has-a relationships between the given classes can be deduced from the nnn given relationships. Is-a relationships can not be circular (apart from the trivial identity "xxx is-a xxx").

\\[20pt]Output\normalsize \textbf{Output}Output

For each query, display the query number (starting at one) and whether the query is true or false.

输出时每行末尾的多余空格,不影响答案正确性

样例输入复制

5 5
Day is-a Time
Appointment is-a Datebook
Appointment is-a Reminder
Appointment has-a Day
Datebook has-a Year
Day is-a Time
Time is-a Day
Appointment has-a Time
Appointment has-a Year
Day is-a Day

样例输出复制

Query 1: true
Query 2: false
Query 3: true
Query 4: true
Query 5: true

题意:

给出若干个is - a, has - a关系,判断询问是否正确

思路:

A is B, B is C   =>   A is C

A is B, B has C  =>  A has C

A has B, B is C  =>  A has C

A has B, B has C  =>  A has C

路径中只要有has就是has, 没有就是is

 

参考:https://acm.taifua.com/archives/gym101673e.html

搜索:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1e4 + 10;

bool vis[N][N][2];
int is[N][N], has[N][N];
map<string, int>mp;
int tot;

void init()
{
    tot = 0;
    mp.clear();
    memset(vis, 0, sizeof(vis));
}

int add(string s)
{
    if(!mp.count(s))
        mp[s] = ++tot;
    return mp[s];
}

void bfs(int u)
{
    queue<pair<int, int> >q;
    vis[u][u][0] = 1;
    q.push(pair<int, int> (u, 0));
    while(q.size())
    {
        pair<int, int> v = q.front();
        q.pop();
        for(int i = 1; i <= tot; ++i)
        {
            if(!vis[u][i][v.second] && is[v.first][i])
            {
                vis[u][i][v.second] = 1;
                q.push(pair<int, int> (i, v.second));
            }
            if(!vis[u][i][1] && has[v.first][i])
            {
                vis[u][i][1] = 1;
                q.push(pair<int, int> (i, 1));
            }
        }
    }
}

int main()
{
    int n, m;
    string a, b, c;
    while(~scanf("%d%d", &n, &m))
    {
        init();
        for(int i = 1; i <= n; ++i)
        {
            cin >> a >> b >> c;
            int id1 = add(a);
            int id2 = add(c);
            if(b[0] == 'i')
            {
                is[id1][id2] = 1;
            }
            else
            {
                has[id1][id2] = 1;
            }
        }
        for(int i = 1; i <= tot; ++i)
        {
            bfs(i);
        }
        for(int i = 1; i <= m; ++i)
        {
            cin >> a >> b >> c;
            bool flag = 0;
            if(b[0] == 'i')
            {
                if(vis[add(a)][add(c)][0])
                    flag = 1;
            }
            else
            {
                if(vis[add(a)][add(c)][1])
                    flag = 1;
            }
            if(flag)
                cout<<"Query "<<i<<": true"<<'\n';
            else
                cout<<"Query "<<i<<": false"<<'\n';
        }
    }
    return 0;
}

floyd求传递闭包:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 510;

int is[N][N], has[N][N];
map<string, int>mp;
int n, m, tot;

void init()
{
    tot = 0;
    mp.clear();
}

int add(string s)
{
    if(!mp.count(s))
        mp[s] = ++tot;
    return mp[s];
}

void floyd1()
{
    for(int k = 1; k <= tot; ++k)
    {
        for(int i = 1; i <= tot; ++i)
        {
            for(int j = 1; j <= tot; ++j)
            {
                is[i][j] = is[i][j] || (is[i][k] && is[k][j]);
            }
        }
    }
}

void floyd2()
{
    for(int k = 1; k <= tot; ++k)
    {
        for(int i = 1; i <= tot; ++i)
        {
            for(int j = 1; j <= tot; ++j)
            {
                has[i][j] = has[i][j] || (has[i][k] && has[k][j]);
                has[i][j] = has[i][j] || (is[i][k] && has[k][j]);
                has[i][j] = has[i][j] || (has[i][k] && is[k][j]);
            }
        }
    }
}

int main()
{
    string a, b, c;
    while(~scanf("%d%d", &n, &m))
    {
        init();
        for(int i = 1; i <= n; ++i)
        {
            cin>>a>>b>>c;
            int id1 = add(a);
            int id2 = add(c);
            is[id1][id1] = 1;
            is[id2][id2] = 1;
            if(b[0] == 'i')
            {
                is[id1][id2] = 1;
            }
            else
            {
                has[id1][id2] = 1;
            }
        }
        floyd1();
        floyd2();
        for(int i = 1; i <= m; ++i)
        {
            cin>>a>>b>>c;
            int id1 = add(a);
            int id2 = add(c);
            bool flag = 0;
            if(b[0] == 'i')
            {
                if(is[id1][id2])
                    flag = 1;
            }
            else
            {
                if(has[id1][id2])
                    flag = 1;
            }
            if(flag)
                cout<<"Query "<<i<<": true"<<'\n';
            else
                cout<<"Query "<<i<<": false"<<'\n';
        }
    }
    return 0;
}