coreBugZJ

此 blog 已弃。

The Social Network, The 36th ACM/ICPC Asia Regional Chengdu Site —— Online Contest

The Social Network

Time Limit: 3000/2000 MS (Java/Others)    Memory Limit: 65768/65768 K (Java/Others)

Problem Description
The social network system (SNS) helps people to keep connecting with their friends. Every user in SNS has a friends list. The user can read news posted by the users in his friends list. Friend relation is symmetric - if A is a friend of B, B is always a friend of A.

Another important function in SNS is friend recommendation. One effective way to recommend friends is recommend by mutual friends. A mutual friend between two users A and B, is a user who is a friend of both A and B. A user can not be a friend of himself. For a specific user A, the system will recommend the user who is not himself or his friend, and has mutual friends with A. If more than one such user exists, recommend the one has most mutual friends with A. If still a tie exists, output all of them.
 

Input
The first line is a integer T (T≤100), the number of test case.
The beginning of each test case is two integers N and Q, the number of friend relationship and the number of query. 1 ≤ N, Q ≤ 1000
The following N lines each contain two different names separated by a single space. Each name consisted by only lowercase letters, and its length is less than or equal to 15. This means the two users are friends. No friend relationship will be given more than once.
The following Q lines each describe a query. Each line contain one user name. The data guarantee that this name appears at least once in above N lines.
 

Output
For each case, you should output one line containing “Case k: ” first, where k indicates the case number and counts from one. Then for each query, output one line, contains one or more names of recommended friends, separate by a single space, sorted by alphabetical order. If no persons can be recommended, output one line contains “-”.
 

Sample Input
1
10 11
hongshu digua
yingying hongshu
xmm hongshu
huaxianzi xmm
tangjiejie huaxianzi
xhmz yingying
digua xhmz
zt tangjiejie
xmm lcy
notonlysuccess ljq
hongshu
digua
yingying
xmm
huaxianzi
tangjiejie
xhmz
zt
lcy
notonlysuccess
ljq
 

Sample Output
Case 1:
xhmz
yingying
digua
digua tangjiejie yingying
hongshu lcy zt
xmm
hongshu
huaxianzi
hongshu huaxianzi
-
-




  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 
  5 #define  N  2002
  6 #define  NAMELEN  17
  7 
  8 /* id 1..nId */
  9 /* id <=> name */
 10 #define  TC  26
 11 #define  TM  100000
 12 struct __Trie
 13 {
 14         struct __Trie * ch[ TC ];
 15         int id;
 16 };
 17 typedef  struct __Trie  Trie;
 18 Trie  trieMem[ TM ];
 19 char  nameMem[ N ][ NAMELEN ];
 20 int nId, totMem;
 21 Trie *root;
 22 
 23 int  getIdFromName( char *name ) {
 24         char *= name;
 25         Trie **pp = &root;
 26         for ( ; ; ) {
 27                 if ( NULL == (*pp) ) {
 28                         *pp = trieMem + totMem++;
 29                         memset( (*pp), 0sizeof(Trie) );
 30                 }
 31                 if ( *p ) {
 32                         pp = &( (*pp)->ch[ (*p) - 'a' ] );
 33                         ++p;
 34                 }
 35                 else {
 36                         if ( (*pp)->id ) {
 37                                 return ((*pp)->id);
 38                         }
 39                         else {
 40                                 (*pp)->id = ++nId;
 41                                 strcpy( nameMem[ nId ], name );
 42                                 return nId;
 43                         }
 44                 }
 45         }
 46         return 0;
 47 }
 48 #define  getNameFromId(id) nameMem[ (id) ]
 49 
 50 char isFri[ N ][ N ];
 51 int  friend[ N ][ N ], numFri[ N ];/* friend[ i ][ 1..numFri[i] ] */
 52 int  mut[ N ][ N ];
 53 
 54 void  init() {
 55         root  = NULL;
 56         nId = 0;
 57         totMem = 0;
 58         memset( isFri, 0sizeof(isFri) );
 59         memset( numFri, 0sizeof(numFri) );
 60         memset( mut, 0sizeof(mut) );
 61 }
 62 
 63 int  cmpNameById( const void *a, const void *b ) {
 64         return strcmp( getNameFromId(*((int*)a)), getNameFromId(*((int*)b)) );
 65 }
 66 
 67 
 68 void  process() {
 69         int i, j, k, x, y;
 70         for ( k = nId; k > 0--k ) {
 71                 for ( i = numFri[ k ]; i > 0--i ) {
 72                         x = friend[ k ][ i ];
 73                         for ( j = i - 1; j > 0--j ) {
 74                                 y = friend[ k ][ j ];
 75                                 if ( 0 == isFri[ x ][ y ] ) {
 76                                         ++mut[ x ][ y ];
 77                                         ++mut[ y ][ x ];
 78                                 }
 79                         }
 80                 }
 81         }
 82 }
 83 
 84 void query( char *name ) {
 85         static int mf[ N ];
 86         int i, j, maxMut = 0, k = 0;
 87         i = getIdFromName( name );
 88         for ( j = nId; j > 0--j ) {
 89                 if ( mut[ i ][ j ] > maxMut ) {
 90                         maxMut = mut[ i ][ j ];
 91                         k = 1;
 92                         mf[ 0 ] = j;
 93                 }
 94                 else if ( mut[ i ][ j ] == maxMut ) {
 95                         mf[ k++ ] = j;
 96                 }
 97         }
 98         if ( maxMut == 0 ) {
 99                 puts( "-" );
100                 return;
101         }
102         qsort( mf, k, sizeof(mf[0]), cmpNameById );
103         printf( "%s", getNameFromId(mf[0]) );
104         for ( i = 1; i < k; ++i ) {
105                 printf( " %s", getNameFromId(mf[i]) );
106         }
107         puts( "" );
108 }
109 
110 int  main() {
111         int m, q, tc, cc, idA, idB;
112         char nameA[ NAMELEN ], nameB[ NAMELEN ];
113         scanf( "%d"&tc );
114         for ( cc = 1; cc <= tc; ++cc ) {
115                 init();
116                 scanf( "%d%d"&m, &q );
117                 while ( m-- > 0 ) {
118                         scanf( "%s%s", nameA, nameB );
119                         idA = getIdFromName( nameA );
120                         idB = getIdFromName( nameB );
121                         if ( (0 == isFri[ idA ][ idB ]) && (idA != idB) ) {
122                                 isFri[ idA ][ idB ] = isFri[ idB ][ idA ] = 1;
123                                 friend[ idA ][ ++numFri[idA] ] = idB;
124                                 friend[ idB ][ ++numFri[idB] ] = idA;
125                         }
126                 }
127                 process();
128                 printf( "Case %d:\n", cc );
129                 while ( q-- > 0 ) {
130                         scanf( "%s", nameA );
131                         query( nameA );
132                 }
133         }
134         return 0;
135 }
136 

posted on 2011-09-11 17:04 coreBugZJ 阅读(336) 评论(0)  编辑 收藏 引用 所属分类: ACM


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理