• <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>
            alpc60 ACM/ICPC程序設計
            成長的路……源
            posts - 20,comments - 42,trackbacks - 0
             

            Team Them Up!

            Time Limit: 1000MS

             

            Memory Limit: 10000K

            Total Submissions: 1440

             

            Accepted: 358

             

            Special Judge

            Description

            Your task is to divide a number of persons into two teams, in such a way, that:

            everyone belongs to one of the teams;

            every team has at least one member;

            every person in the team knows every other person in his team;

            teams are as close in their sizes as possible.

            This task may have many solutions. You are to find and output any solution, or to report that the solution does not exist.

            Input

            For simplicity, all persons are assigned a unique integer identifier from 1 to N.

            The first line in the input file contains a single integer number N (2 <= N <= 100) - the total number of persons to divide into teams, followed by N lines - one line per person in ascending order of their identifiers. Each line contains the list of distinct numbers Aij (1 <= Aij <= N, Aij != i) separated by spaces. The list represents identifiers of persons that ith person knows. The list is terminated by 0.

            Output

            If the solution to the problem does not exist, then write a single message "No solution" (without quotes) to the output file. Otherwise write a solution on two lines. On the first line of the output file write the number of persons in the first team, followed by the identifiers of persons in the first team, placing one space before each identifier. On the second line describe the second team in the same way. You may write teams and identifiers of persons in a team in any order.

            Sample Input

            5
            2 3 5 0
            1 4 5 3 0
            1 2 5 0
            1 2 3 0
            4 3 2 1 0

            Sample Output

            3 1 3 5
            2 2 4

            Source

            Northeastern Europe 2001

             

             

            題目大意:把n個人分成2各組,每一個人有他所認識的人。所分的組有四點要求:

            1、 每個人都必需屬于一個組。

            2、 每個組至少有一個人。

            3、 每個組里面的每個人必需互相認識。

            4、 兩個組的成員應盡量接近。

            首先分析這道題目,題目給出的是一個有向圖,即如果有A認識B,但不一定有B認識A。但是在所分配的組里面,任意兩個人都要互相認識。

            1、 先讀入數據建立有向圖,然后對這個有向圖進行處理,如果兩個點之間的邊是單向邊,就認為兩個點之間無邊(因為這兩個人不互相認識),對于兩個點間的雙向邊,即建立一條無向邊(這兩個人互相認識),這樣就可以把一個有向圖轉化為一個無向圖。

            2、 將這個無向圖轉化為它的反圖。即有邊的把邊刪去,無邊的添上一條邊。(其實12步在程序實現時可以一次完成)。

            3、 對轉換后的反圖求極大連通分量。想想就會明白剛才為什么要求反圖,可以看到在這個反圖中的不同的連通分量中的兩個人都是互相認識的!!!接下來很關鍵,那些互不認識的人就在一個連通分量里面。

            4、 在做DFS求連通分量的時候,同時對連通分量中的點染色(01),如果一個點顏色為0,那么所有和它相鄰的點與它的顏色應該不同(標記為1)。這是因為反圖中相鄰的兩個人都是不認識的(回顧剛才反圖的作用)。這樣DFS結束后,就可以根據顏色把連通分量中的點分成兩個組s0s1,在不同兩個組的人是不可能分到一個team內的。到這里要做一個特判,對于s0s1組里的任意兩個人p,q如果反圖中存在一條邊(p,q),說明無解,輸出"No solution"

            5、 求出了所有的連通分量,對于第i個連通分量都把其節點分為兩個組s1is2i。這時要做的就是把所有的s1is2i分配到team1team2中去,使team1的總和與team2的總和差值最小。就可以用背包DP了。
            dp[i][j]
            表示第i個連通分量達到j的差值,true為可達,false為不可達。
            狀態轉移方程:
            dp[i][j+si0-si1]=true if dp[i-1][j] == true
            dp[i][j-si0+si1]=true if dp[i-1][j] == true
            同時記錄轉移路徑,差值j的范圍是-100~+100可以坐標平移。
            最后在dp[m][i]m是最后一個連通塊數)中找出值為true的最小i值。輸出答案。


            posted on 2008-08-08 00:51 飛飛 閱讀(3482) 評論(2)  編輯 收藏 引用 所屬分類: ACM/ICPC

            FeedBack:
            # re: POJ 1112 Team Them Up! 求補圖,連通分量,DP
            2008-09-04 08:47 | ssadwlll
            不愧是國防科技大學的大牛!!
              回復  更多評論
              
            # re: POJ 1112 Team Them Up! 求補圖,連通分量,DP
            2012-07-30 21:50 | Colleen
            nice  回復  更多評論
              
            国产人久久人人人人爽| 99久久精品无码一区二区毛片 | 91精品国产91久久| 99久久综合国产精品二区| 午夜视频久久久久一区| 久久国产免费观看精品3| 精品国产一区二区三区久久| 亚洲人AV永久一区二区三区久久| 精产国品久久一二三产区区别| 国内精品久久人妻互换| 成人午夜精品久久久久久久小说| 国产精品久久亚洲不卡动漫| 国产ww久久久久久久久久| 久久人妻少妇嫩草AV蜜桃| 日本免费久久久久久久网站| 久久人人爽人人爽人人片AV不| 影音先锋女人AV鲁色资源网久久| 青草国产精品久久久久久| 精品视频久久久久| 九九久久精品国产| 久久w5ww成w人免费| 无码人妻久久一区二区三区蜜桃| 一级做a爰片久久毛片看看| 久久精品国产99久久久| 麻豆精品久久久久久久99蜜桃| 亚洲国产精品一区二区久久| 亚洲欧美国产日韩综合久久| 99久久精品免费看国产免费| 久久精品国产99国产精品澳门| 亚洲精品高清国产一线久久| 一本大道久久东京热无码AV| 青青草国产精品久久| 99久久超碰中文字幕伊人| 一本一道久久综合狠狠老| 一本一本久久a久久精品综合麻豆| 久久夜色撩人精品国产| 国产亚洲成人久久| 91精品国产91久久久久久蜜臀| 久久国产精品-国产精品| 伊人久久大香线蕉av不卡| 亚洲人成伊人成综合网久久久|