• <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 飛飛 閱讀(3474) 評論(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  回復  更多評論
              
            天堂久久天堂AV色综合| 九九热久久免费视频| 久久久久久国产精品无码超碰| 九九精品99久久久香蕉| 国产成人久久精品麻豆一区| 久久夜色精品国产噜噜亚洲a| 狠狠色丁香婷婷久久综合| 国产亚洲欧美精品久久久| 国产成人无码精品久久久免费| 一本色道久久综合| 69久久精品无码一区二区| 久久综合色之久久综合| 好久久免费视频高清| 午夜福利91久久福利| 青青国产成人久久91网| 国内精品久久久久影院老司 | 精品国产青草久久久久福利| 精品永久久福利一区二区| 欧美久久天天综合香蕉伊| 国产精品99久久久久久人| 99久久国产综合精品女同图片| 狠狠久久综合| 久久精品这里热有精品| 久久国产精品一国产精品金尊| 精品久久久久久久国产潘金莲| 久久国产精品免费一区二区三区 | 亚洲精品国产综合久久一线| 久久亚洲欧美日本精品| 国产午夜久久影院| 国产情侣久久久久aⅴ免费| 精品熟女少妇AV免费久久| 亚洲美日韩Av中文字幕无码久久久妻妇 | 久久电影网一区| 久久偷看各类wc女厕嘘嘘| 国产毛片欧美毛片久久久| 久久无码AV一区二区三区| 久久免费视频一区| 欧美久久久久久| 久久精品亚洲中文字幕无码麻豆| 亚洲精品乱码久久久久久蜜桃不卡| 久久久久青草线蕉综合超碰|