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

            ACM___________________________

            ______________白白の屋
            posts - 182, comments - 102, trackbacks - 0, articles - 0
            <2010年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(24)

            隨筆分類(332)

            隨筆檔案(182)

            FRIENDS

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋    

             

            題目地址:

                  http://acm.hdu.edu.cn/showproblem.php?pid=2473 

            題目描述:

            Junk-Mail Filter

            Time Limit: 15000/8000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
            Total Submission(s): 1785    Accepted Submission(s): 521


            Problem Description
            Recognizing junk mails is a tough task. The method used here consists of two steps:
            1) Extract the common characteristics from the incoming email.
            2) Use a filter matching the set of common characteristics extracted to determine whether the email is a spam.

            We want to extract the set of common characteristics from the N sample junk emails available at the moment, and thus having a handy data-analyzing tool would be helpful. The tool should support the following kinds of operations:

            a) “M X Y”, meaning that we think that the characteristics of spam X and Y are the same. Note that the relationship defined here is transitive, so
            relationships (other than the one between X and Y) need to be created if they are not present at the moment.

            b) “S X”, meaning that we think spam X had been misidentified. Your tool should remove all relationships that spam X has when this command is received; after that, spam X will become an isolated node in the relationship graph.

            Initially no relationships exist between any pair of the junk emails, so the number of distinct characteristics at that time is N.
            Please help us keep track of any necessary information to solve our problem.
             

            Input
            There are multiple test cases in the input file.
            Each test case starts with two integers, N and M (1 ≤ N ≤ 105 , 1 ≤ M ≤ 106), the number of email samples and the number of operations. M lines follow, each line is one of the two formats described above.
            Two successive test cases are separated by a blank line. A case with N = 0 and M = 0 indicates the end of the input file, and should not be processed by your program.
             

            Output
            For each test case, please print a single integer, the number of distinct common characteristics, to the console. Follow the format as indicated in the sample below.
             

            Sample Input
            5 6 M 0 1 M 1 2 M 1 3 S 1 M 1 2 S 3 3 1 M 1 2 0 0
             

            Sample Output
            Case #1: 3 Case #2: 2
             

            題目分析:

                   題目的意思大概就是 有N 封郵件, 編號 0 -> N-1,  然后有2種操作,  M : 合并操作, 將 2 種郵件合并為一種.

                                                                                                                                      S  : 分離操作, 將一封郵件獨立出去, 單獨占一個集合.

                  最后題目要求統計 集合的 個數.   從這里可以很容易的看出, 這是一個 并查集的題目, 不過按樸素方法來做的話, 一般都會 TLE.

            加上數據量很大 ,  不要使用 cin , 會超時. 而且一般來說 G ++ 和 C++ 在處理大量數據的時候會有1倍的時差 !!! 所以一般建議使用

            C++ 提交代碼.

             

             先看代碼 :

             /*

            MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋

                      http://www.cnblog.com/MiYu

            Author By : MiYu

            Test      : 1

            Program   : 2473

            */


            #include <iostream>

            #include <algorithm>

            using namespace std;

            int set[1350005];

            int a[125000];

            int N,M;

            int inline find ( int x )

            {

                return x != set[x] ? set[x] = find ( set[x] ) : set[x]; 

            void inline merge ( int x, int y )

            {

                 x = find ( x );

                 y = find ( y );

                 if ( x == y )  return ;

                 set[x] = y; 

            }

            int main ()

            {

                int ca = 1;

                while ( scanf ( "%d%d",&N,&M ), M || N )

                {

                        for ( int i = 0; i < N; ++ i )

                              set[i] = i+N;

                        for ( int i = N; i <= N + N + M; ++ i )

                              set[i] = i;          //       <------------------------------這是關鍵, 雖然空間的消耗比較大, 但是節省了大量時間, 這樣處理的目的是將0 -> N-1 的 節點處理成葉子節點

                                                     //                                                       這樣在對這些 節點做 S 操作的時候就不會影響到其他的節點, 而 find 操作是帶路徑壓縮的, 所以就保證了我們所                                            //                                                       有要處理的節點一直是葉子節點 !!!

                        int sep = N + N;

                        int x,y; char ch[5]; 

                        for ( int i = 0; i != M; ++ i )

                        {

                              scanf ( "%s",ch ); 

                              switch ( ch[0] )

                              {

                                       case 'M': scanf ( "%d%d",&x,&y ); merge ( x,y ); break;

                                       case 'S': scanf ( "%d",&x ); set[x] = sep ++;    break;                   //初始化操作就是為這一步準備的

                              }

                        } 

                        for ( int i = 0; i != N; ++ i )

                              a[i] = find ( i );

                        sort ( a, a + N );   

                        int nCount = 1;

                        for ( int i = 1; i < N; ++ i )

                              if ( a[i] != a[i-1] ) nCount ++;

                        printf("Case #%d: %d\n",ca++,nCount);

                }

                return 0;

            }


             

            一本大道加勒比久久综合| 久久久久久久久久久免费精品 | 男女久久久国产一区二区三区| 香蕉久久夜色精品国产尤物| 久久久精品国产免大香伊 | 亚洲精品国产字幕久久不卡| 2020久久精品亚洲热综合一本| 久久综合亚洲鲁鲁五月天| 国内精品久久久久影院日本| 国产巨作麻豆欧美亚洲综合久久| 少妇人妻综合久久中文字幕| 日本一区精品久久久久影院| 色老头网站久久网| 国产精品嫩草影院久久| 色综合久久久久综合体桃花网 | 国产精品久久久久影视不卡| 色欲综合久久躁天天躁| 国产精品久久国产精品99盘| 久久人人爽人人人人爽AV| 99热成人精品免费久久| 久久精品无码专区免费青青| 超级碰碰碰碰97久久久久| www亚洲欲色成人久久精品| 久久亚洲AV无码精品色午夜| 久久久久综合中文字幕| 久久综合中文字幕| 色婷婷综合久久久久中文一区二区| 久久久WWW免费人成精品| 久久婷婷国产麻豆91天堂| 午夜欧美精品久久久久久久| 亚洲午夜福利精品久久| 性高朝久久久久久久久久| 久久一区二区免费播放| 久久久精品人妻无码专区不卡| 97久久精品人人澡人人爽| 色综合合久久天天综合绕视看| 精品无码久久久久国产| 国产91色综合久久免费| 青青草国产精品久久久久| 亚洲国产精久久久久久久| 国产ww久久久久久久久久|