• <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>
            隨筆 - 87  文章 - 279  trackbacks - 0
            <2010年5月>
            2526272829301
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            潛心看書研究!

            常用鏈接

            留言簿(19)

            隨筆分類(81)

            文章分類(89)

            相冊

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 218017
            • 排名 - 117

            最新評論

            閱讀排行榜

            評論排行榜

            Girls and Boys

            Time limit: 10 Seconds?? Memory limit: 32768K??
            Total Submit: 628?? Accepted Submit: 188??

            the second year of the university somebody started a study on the romantic relations between the students. The relation “romantically involved” is defined between one girl and one boy. For the study reasons it is necessary to find out the maximum set satisfying the condition: there are no two students in the set who have been “romantically involved”. The result of the program is the number of students in such a set.

            The input contains several data sets in text format. Each data set represents one set of subjects of the study, with the following description:

            the number of students
            the description of each student, in the following format
            student_identifier:(number_of_romantic_relations) student_identifier1 student_identifier2 student_identifier3 ...
            or
            student_identifier:(0)

            The student_identifier is an integer number between 0 and n-1, for n subjects.
            For each given data set, the program should write to standard output a line containing the result.

            An example is given in Figure 1.


            Input

            7
            0: (3) 4 5 6
            1: (2) 4 6
            2: (0)
            3: (0)
            4: (2) 0 1
            5: (1) 0
            6: (2) 0 1
            3
            0: (2) 1 2
            1: (1) 0
            2: (1) 0


            Output

            5
            2

            #include? < iostream > ?
            using ? namespace ?std;

            const ? int ?MAXN? = ? 1001 ;
            int ?uN,?vN;?? // u,v數目?
            bool ?g[MAXN][MAXN]; // g[i][j]?表示?xi與yj相連?
            bool ?p[MAXN][MAXN];
            int ?xM[MAXN],?yM[MAXN];? // ?輸出量?
            bool ?chk[MAXN];? // 輔助量?檢查某輪?y[v]是否被check?

            int ?sign[MAXN];
            int ?N;

            bool ?SearchPath( int ?u)
            {
            ????
            int ?v;
            ????
            for ?(v = 0 ;?v < vN;?v ++ )
            ????
            {
            ????????
            if ?(g[u][v]? && ? ! chk[v])
            ????????
            {
            ????????????chk[v]?
            = ? true ;
            ????????????
            if ?(yM[v]? == ? - 1 ? || ?SearchPath(yM[v]))?
            ????????????
            {
            ????????????????yM[v]?
            = ?u;
            ????????????????xM[u]?
            = ?v;
            ????????????????
            return ? true ;
            ????????????}

            ????????}

            ????}

            ????
            return ? false ;
            }



            int ?MaxMatch()
            {
            ????
            int ?u;
            ????
            int ?ret? = ? 0 ;
            ????memset(xM,?
            - 1 ,? sizeof (xM));
            ????memset(yM,?
            - 1 ,? sizeof (yM));
            ????
            for ?(u = 0 ;?u < uN;?u ++ )
            ????
            {
            ????????
            if ?(xM[u]? == ? - 1 )
            ????????
            {
            ????????????memset(chk,?
            false ,? sizeof (chk));
            ????????????
            if ?(SearchPath(u))?ret ++ ;
            ????????}

            ????}

            ????
            return ?ret;
            }


            void ?SetSign( int ?v,? int ?s)
            {
            ????
            int ?i;
            ????sign[v]?
            = ?s;
            ????
            for ?(i = 0 ;?i < N;?i ++ )
            ????????
            if ?(sign[i]? == ? - 1 ? && ?p[v][i])
            ????????????SetSign(i,?
            1 - s);?????
            }


            void ?Solve()
            {
            ????
            int ?i,?j;?
            ????
            int ?tU,?tV;
            ????
            int ?num;
            ????memset(g,?
            false ,? sizeof (g));
            ????memset(p,?
            false ,? sizeof (p));
            ????memset(sign,?
            - 1 ,? sizeof (sign));
            ????
            for ?(i = 0 ;?i < N;?i ++ )
            ????
            {
            ????????scanf(
            " \n%d:?(%d) " ,? & tU,? & num);
            ????????
            for ?(j = 0 ;?j < num;?j ++ )
            ????????
            {
            ????????????scanf(
            " %d " ,? & tV);
            ????????????p[tU][tV]?
            = ? true ;
            ????????}

            ????}
            ?
            ????
            ????
            // -------------DFS標號法(劃分二分圖)--------------------?
            ???? /* ******************************************
            ????鄰接表的DFS標號:
            ????void?setmark(int?v,int?sign)
            ????{
            ????????sig[v]=sign;
            ????????int?i;
            ????????for?(i=0;i<nu[v];i++)
            ????????????if?(!sig[d[v][i]])
            ????????????????setmark(d[v][i],sign^3);
            ????}?
            ????for?(v=0;v<n;v++)
            ????????if?(!sig[v])?setmark(v,1);
            ????*******************************************
            */

            ????
            for ?(i = 0 ;?i < N;?i ++ )
            ????????
            if ?(sign[i]? == ? - 1 )?SetSign(i,? 1 );
            ????
            // ------------------------------------------????
            ????????
            ????
            for ?(i = 0 ;?i < N;?i ++ )
            ????
            {
            ????????
            if ?(sign[i]? == ? 1 )
            ????????
            {
            ????????????
            for ?(j = 0 ;?j < N;?j ++ )
            ????????????????
            if ?(p[i][j])?g[i][j]? = ? true ;
            ????????}

            ????}
            ????????????
            ????uN?
            = ?vN? = ?N;
            ????printf(
            " %d\n " ,?N - MaxMatch());?
            }
            ?

            int ?main()
            {
            ????
            while ?(scanf( " %d " ,? & N)? != ?EOF)
            ????
            {
            ????????Solve();
            ????}

            ????
            return ? 0 ;
            }

            posted on 2006-10-01 22:53 閱讀(583) 評論(0)  編輯 收藏 引用 所屬分類: ACM題目
            久久伊人精品青青草原高清| 国产精品无码久久综合| 国产AV影片久久久久久| 亚洲欧洲精品成人久久曰影片| 亚洲AV无码久久精品狠狠爱浪潮 | 狠狠色丁香婷婷久久综合不卡 | 精品伊人久久大线蕉色首页| 999久久久免费国产精品播放| 99久久无色码中文字幕人妻| 久久久久久A亚洲欧洲AV冫| 久久精品国产第一区二区三区| 亚洲国产高清精品线久久| 久久精品国产99国产精品导航 | 国产免费久久精品99re丫y| 97久久精品人人做人人爽| 综合久久一区二区三区| 久久99国产精品久久99果冻传媒| 久久久这里有精品中文字幕| 色综合久久中文综合网| 99精品国产99久久久久久97 | 久久精品国产免费一区| 无码久久精品国产亚洲Av影片| 91麻豆精品国产91久久久久久| 99精品久久久久久久婷婷| 精品久久久久久无码中文字幕 | 一级a性色生活片久久无| 亚洲精品无码久久久久去q| 国产精品成人无码久久久久久| 欧美丰满熟妇BBB久久久| 精品国产91久久久久久久a| 色综合久久综合中文综合网| 伊人 久久 精品| 久久99精品国产麻豆蜜芽| 亚洲国产精品人久久| 91精品国产9l久久久久| 久久99精品久久久久久| 精品久久久久久亚洲精品| 亚洲AV成人无码久久精品老人| 伊人久久精品无码二区麻豆| 亚洲伊人久久成综合人影院 | 久久久精品人妻一区二区三区蜜桃|