• <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>

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

            亚洲精品tv久久久久久久久| 久久大香香蕉国产| 欧美亚洲另类久久综合婷婷| 国内精品伊人久久久久影院对白 | 亚洲午夜久久久影院| 久久精品aⅴ无码中文字字幕不卡 久久精品aⅴ无码中文字字幕重口 | 久久综合给久久狠狠97色| 97久久天天综合色天天综合色hd| 国产精品欧美久久久久天天影视| 亚洲精品高清一二区久久| 精品久久久噜噜噜久久久| 欧美午夜A∨大片久久| 国内精品伊人久久久久av一坑| 久久97久久97精品免视看秋霞| 亚洲中文久久精品无码ww16| 国产精品无码久久久久| 精品无码久久久久国产| 久久精品国产2020| 久久99精品久久久久久9蜜桃| 国产亚洲色婷婷久久99精品| 人妻丰满?V无码久久不卡| 亚洲一区二区三区日本久久九| 综合久久一区二区三区| 99久久精品费精品国产| 国产精品久久久福利| 精品久久久久久国产| 亚洲国产成人久久综合野外| 激情综合色综合久久综合| 欧美精品一区二区精品久久| 欧美一区二区三区久久综合| 亚洲色大成网站WWW久久九九| 婷婷国产天堂久久综合五月| 久久久免费观成人影院| 久久国产精品免费| 欧美性猛交xxxx免费看久久久 | 亚洲国产综合久久天堂| 色8激情欧美成人久久综合电| 久久国产三级无码一区二区| 狠狠色丁香婷婷综合久久来来去| 国内精品伊人久久久久网站| 久久亚洲AV无码西西人体|