HRBUST 1314 火影忍者之～纲手【MAP】

火影忍者之～纲手

Time Limit: 3000 MS Memory Limit: 65536 K Total Submit: 246(78 users) Total Accepted: 101(69 users) Rating: Special Judge: No

Description

因为大蛇丸的捣乱，木叶忍者村痛失了和蔼的三代火影，所以身为三代火影徒弟之一的纲手不得不接受木叶村火影的职务～，因为刚刚上任，所以纲手大人需要对木叶村主要忍者的实力有个了解，以方便以后分配任务，所以我们需要统计一下每个忍者的实力高低，作为刚刚通过公务员选拔的你，这可是个很好的表现机会～你需要做的是将所有给定忍者部分实力高低关系，然后在需要的时候能够快速的查找到.

Input

给出一个整数n，然后n行每行给出两个名字，表示前一个忍者强于后一个，然后是一个整数m，表示m个查找，然后是m行，每行也是两个名字。输入到文件尾。忍者的个数在1000以内，名字不长于20，n<1000000,m<=1000。

Output

对于每个查找，输出两个忍者的强弱关系，如果前一个强于后一个，输出“win”，如果前一个弱于后一个，输出”lose”,如果不能确定或查找不到，输出”unknown”。(强弱关系不能传递。）

Sample Input

3 abc bcd def fgh def abc 2 bcd fgh fgh def

Sample Output

unknown lose

Source

2012 Spring Contest 3 - STL

Author

拂晓

原本觉得应该是并查集，。。。然后发现没有强弱关系传递。。。嗯，，，还是想麻烦了。。

但这题还是一个很好的思路题。。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;

int vis[1005][1005];///记录比赛情况，就是记录谁和谁比赛过

int main()
{

    char namea[25];
    char nameb[25];

    map<string,int>m;///确立map对立关系

    int n;
    while(cin>>n)
    {
        m.clear();///别忘清空
        memset(vis,0,sizeof(vis));

        int flag=0;

        for(int i=0; i<n; i++)
        {
            scanf("%s %s",namea,nameb);

            if(!m[namea])
            {
                m[namea]=flag++;///如果没有比赛过，就自增。
            }
            if(!m[nameb])
            {
                m[nameb]=flag++;
            }
            vis[m[namea]][m[nameb]]=1;
        }
        int n2;
        scanf("%d",&n2);

        while(n2--)
        {

            scanf("%s %s",namea,nameb);
            /*
            unknow情况有以下几种
            !m[namea]||!m[nameb] 代表两者都没有去比赛
            vis[m[namea]][m[nameb]]&&vis[m[nameb]][m[namea]]  代表A战胜了B B又战胜了A，互相矛盾
            vis[m[namea]][m[nameb]]==0&&vis[m[nameb]][m[namea]]==0  代表两者没有必过赛
            */


            if(!m[namea]||!m[nameb]||(vis[m[namea]][m[nameb]]&&vis[m[nameb]][m[namea]])||(vis[m[namea]][m[nameb]]==0&&vis[m[nameb]][m[namea]]==0))
            {
                printf("unknown\n");
            }
            else if(vis[m[namea]][m[nameb]])
            {
                printf("win\n");
            }
            else if(vis[m[nameb]][m[namea]])
            {
                printf("lose\n");
            }

        }
    }
    return 0;
}