青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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 閱讀(351) 評(píng)論(0)  編輯 收藏 引用 所屬分類: ACM

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            久久中文精品| 久久久久综合一区二区三区| 欧美在线影院| 午夜精品视频在线观看一区二区| 欧美午夜理伦三级在线观看| 亚洲欧美日韩电影| 亚洲专区在线| 伊人狠狠色j香婷婷综合| 欧美xx69| 欧美日韩系列| 欧美亚洲网站| 久久中文字幕一区| 在线综合亚洲| 亚洲欧美日韩直播| 激情久久五月天| 亚洲精品日韩精品| 国产精品推荐精品| 欧美成人免费在线视频| 欧美精品在线免费观看| 欧美一区二区久久久| 久久亚洲视频| 亚洲精品视频啊美女在线直播| 国产视频不卡| 99国产精品私拍| 亚洲欧美日韩中文在线制服| 亚洲国产成人精品久久久国产成人一区| 欧美精品免费播放| 性一交一乱一区二区洋洋av| 亚洲男女自偷自拍图片另类| 激情综合久久| 在线视频你懂得一区| 影音先锋亚洲视频| 日韩视频第一页| 亚洲电影免费观看高清| 亚洲网站视频福利| 91久久久久久国产精品| 午夜免费电影一区在线观看| 99精品国产福利在线观看免费| 欧美专区在线| 亚洲欧美国产一区二区三区| 欧美高清自拍一区| 另类酷文…触手系列精品集v1小说| 欧美日韩国语| 欧美激情视频在线播放| 国产一区二区三区无遮挡| av成人天堂| 亚洲美女福利视频网站| 久久综合999| 久久久久久久综合色一本| 欧美午夜影院| 亚洲免费观看高清完整版在线观看| 激情文学一区| 亚洲高清视频一区| 欧美一区二区在线播放| 亚洲欧美视频一区| 欧美性猛交xxxx乱大交蜜桃| 亚洲三级影院| 亚洲欧洲另类| 欧美高清视频免费观看| 亚洲高清在线观看一区| 亚洲国产精品黑人久久久| 久久久天天操| 欧美成年视频| 亚洲国产裸拍裸体视频在线观看乱了| 欧美影视一区| 久久久亚洲人| 影音先锋在线一区| 久久综合国产精品| 欧美国产三级| 亚洲精品女av网站| 欧美精品一区二区三区很污很色的 | 久久久久久久综合狠狠综合| 国产女主播在线一区二区| 亚洲一区二区动漫| 久久久精彩视频| 伊人成年综合电影网| 久久亚洲欧洲| 亚洲欧洲视频在线| 亚洲综合色丁香婷婷六月图片| 欧美午夜一区| 欧美在线三级| 亚洲国产精品va在看黑人| 亚洲日本黄色| 国产精品久久九九| 一本色道久久综合亚洲精品婷婷| 亚洲手机在线| 国产日韩欧美一区二区三区在线观看| 欧美亚洲日本一区| 免费观看成人鲁鲁鲁鲁鲁视频 | 欧美国产日本在线| 亚洲精品在线二区| 国产精品成人观看视频免费| 午夜欧美大片免费观看| 卡通动漫国产精品| 一区二区三区久久精品| 国产女精品视频网站免费| 久久久免费av| 一本色道久久综合亚洲精品按摩| 午夜精品福利一区二区三区av| 红桃视频一区| 欧美午夜视频| 女主播福利一区| 亚洲午夜av在线| 亚洲第一黄网| 久久精品视频在线看| 一区二区av在线| 韩国女主播一区| 欧美婷婷六月丁香综合色| 久久久精品国产免大香伊| 99精品免费视频| 欧美国产综合视频| 欧美专区在线| 亚洲午夜在线观看| 亚洲电影免费观看高清完整版在线观看| 欧美精品麻豆| 麻豆国产精品777777在线| 午夜精品久久久久久99热| 亚洲精品免费在线播放| 免费观看成人鲁鲁鲁鲁鲁视频| 午夜精品理论片| 日韩一级裸体免费视频| 激情成人av在线| 国产欧美日韩另类一区| 欧美日韩理论| 欧美精品福利在线| 免费看的黄色欧美网站| 欧美与黑人午夜性猛交久久久| 一本色道综合亚洲| 亚洲欧洲综合| 亚洲黄色一区| 亚洲福利专区| 欧美激情一区二区三区不卡| 久久免费视频在线| 久久久噜久噜久久综合| 午夜精品视频一区| 亚洲综合色视频| 亚洲一区自拍| 亚洲一区二区三区激情| 在线亚洲一区观看| 一区二区三区成人精品| 亚洲精品国产精品久久清纯直播| 国产一区二区三区无遮挡| 国产日韩欧美在线看| 国产亚洲一区二区三区在线播放| 国产精品一区亚洲| 国产丝袜一区二区| 国产专区综合网| 一区二区三区在线不卡| 狠狠久久亚洲欧美| 在线播放豆国产99亚洲| 亚洲国产精品999| 亚洲免费黄色| 亚洲一区二区三区成人在线视频精品| 一本久久综合| 午夜精品偷拍| 久久久久久电影| 欧美福利电影在线观看| 亚洲黄一区二区三区| 亚洲精品一二区| 亚洲一区二区毛片| 久久aⅴ国产欧美74aaa| 麻豆91精品91久久久的内涵| 欧美国产日韩一区二区在线观看 | 欧美一区影院| 免费一级欧美片在线播放| 欧美激情在线免费观看| 国产精品二区影院| 精品福利电影| 亚洲一区www| 久久久久久久久久看片| 亚洲观看高清完整版在线观看| 亚洲激情社区| 午夜综合激情| 欧美激情一区二区久久久| 国产精品乱子乱xxxx| 1024精品一区二区三区| 一区二区三区四区国产| 久久精品久久99精品久久| 欧美肥婆在线| 亚洲永久精品大片| 免费在线视频一区| 国产区二精品视| 日韩一区二区免费看| 欧美一区在线视频| 亚洲激情第一区| 欧美一区二区三区四区视频| 欧美激情久久久久久| 国产亚洲人成a一在线v站| 亚洲美女黄色片| 玖玖精品视频| 午夜精品视频在线观看一区二区| 米奇777超碰欧美日韩亚洲| 国产精品最新自拍| 一区二区三区四区精品| 你懂的成人av| 欧美中文在线观看国产| 国产精品久久久久久久电影| 亚洲激情第一页| 卡通动漫国产精品| 欧美一区二区三区在线看|