codevs 2639 约会计划
codevs 2639 约会计划
题目描述Description
cc是个超级帅哥,口才又好,rp极高(这句话似乎降rp),又非常的幽默,所以很多mm都跟他关系不错。然而,最关键的是,cc能够很好的调解各各妹妹间的关系。mm之间的关系及其复杂,cc必须严格掌握她们之间的朋友关系,好一起约她们出去,cc要是和不是朋友的两个mm出去玩,后果不堪设想……
cc只掌握着一些mm之间的关系,但是cc比较聪明,他知道a和b是朋友,b和c 是朋友,那么a和c也是朋友。
下面给出m对朋友关系, cc 定了p次约会,每次约会找两个mm,如果这两个mm是朋友,那么不会出乱子,输出‘safe',要是不是朋友,那么cc必然会挨……,输出‘cc cry'
//这个时候,和蔼可亲的GTBA就要提醒广大的兄弟姐妹们,以后交往一定要谨慎。cc这种人见一次拖下去打傻就够了。
输入描述Input Description
第一行为n,m,p。n为mm的数量,cc知道m对朋友关系,有p次约会。
2到n+1 行,每行一个字符串,为第i个mm的名字。{字符串长度<=11,且全大写}
以下m行,每行两个字符串,用空格隔开 ,为有朋友关系的两个mm的名字。
以下p行,每行为两个字符串,用空格隔开,为这p次约会中两个mm的名字。
{保证数据不会出现没有出现过的名字}
//话说世界上重名的那么多,你是怎么保证一定不会重名呢。
输出描述Output Description
输出P行表示第i次约会的情况,输出‘safe'或者‘cc cry'
//哇,这个cc cry真是油腻。
数据范围及提示 Data Size & Hint
0<m<=2008;0<p<=2008
//这个cc真有钱,一年不断约会是么,败家子,不过他以为妹子们真的傻么,没准在策划着算计他呢。
嗯,继续搞怪,进入正题。
突然发现自己没有样例输入输出;
样例输入 Sample Input:
3 1 1
AAA
BBB
CCC
AAACCC
AAA BBB
样例输出 Sample Output
cc cry //emmm,活该
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<map> 5 using namespace std; 6 string a,b,s; 7 int n,m,p; 8 map<string,string>f; 9 string find(string x){ 10 if(f[x]!=x) return f[x]=find(f[x]); 11 return x; 12 } 13 void unio(string x,string y){ 14 if(find(x)!=find(y)) f[f[y]]=f[x]; 15 } 16 int main(){ 17 scanf("%d%d%d",&n,&m,&p); 18 for(int i=1;i<=n;i++) 19 cin>>s,f[s]=s; 20 for(int i=1;i<=m;i++) 21 cin>>a>>b,unio(a,b); 22 for(int i=1;i<=p;i++){ 23 cin>>a>>b; 24 if(find(a)==find(b)) 25 printf("safe\n"); 26 else 27 printf("cc cry\n"); 28 } 29 return 0; 30 }
用map储存一下,没办法,谁叫她们的名字都是字母呢。然后,跑一遍最小生成树?就好了。
再提醒大江南北的兄弟姐妹们一遍,交往需谨慎,万一整天戴着绿帽子多尴尬啊。
要嫁就嫁灰太狼~~
一世安宁