火影忍者之～纲手
|
||||||
| 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;
}