• <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>
            posts - 74,  comments - 33,  trackbacks - 0

            For any school, it is hard to find a feasible accommodation plan with every student assigned to a suitable apartment while keeping everyone happy, let alone an optimal one. Recently the president of University ABC, Peterson, is facing a similar problem. While Peterson does not like the idea of delegating the task directly to the class advisors as so many other schools are doing, he still wants to design a creative plan such that no student is assigned to a room he/she dislikes, and the overall quality of the plan should be maximized. Nevertheless, Peterson does not know how this task could be accomplished, so he asks you to solve this so-called "interesting" problem for him.
            Suppose that there are N students and M rooms. Each student is asked to rate some rooms (not necessarily all M rooms) by stating how he/she likes the room. The rating can be represented as an integer, positive value meaning that the student consider the room to be of good quality, zero indicating neutral, or negative implying that the student does not like living in the room. Note that you can never assign a student to a room which he/she has not rated, as the absence of rating indicates that the student cannot live in the room for other reasons.
            With limited information available, you've decided to simply find an assignment such that every student is assigned to a room he/she has rated, no two students are assigned to the same room, and the sum of rating is maximized while satisfying Peterson's requirement. The question is … what exactly is the answer?

            Input

            There are multiple test cases in the input file. Each test case begins with three integers, N, M, and E (1 <= N <= 500, 0 <= M <= 500, 0 <= E <= min(N * M, 50000)), followed by E lines, each line containing three numbers, Si, Ri, Vi, (0 <= Si < N, 0 <= Ri < M, |Vi| <= 10000), describing the rating Vi given by student Si for room Ri. It is guaranteed that each student will rate each room at most once.
            Each case is followed by one blank line. Input ends with End-of-File.

            Output

            For each test case, please output one integer, the requested value, on a single line, or -1 if no solution could be found. Use the format as indicated in the sample output.

            Sample Input

            3 5 5
            0 1 5
            0 2 7
            1 1 6
            1 2 3
            2 4 5

            1 1 1
            0 0 0

            1 1 0

            Sample Output

            Case 1: 18
            Case 2: 0
            Case 3: -1
            人品差沒得說,剛才寫了那么多居然沒有提交成功,第二次鄙視自己居然少寫判斷條件!!!
            本校的7016還一直TLE!!!
            本題就是普通的KM,外加判斷是否能構成完美匹配!!!
            ------------------------------------------------------------------------------------------------------------------
            本校也AC了,自己寫了個鄰接表!!!

            posted on 2009-03-24 21:03 KNIGHT 閱讀(206) 評論(0)  編輯 收藏 引用
            <2025年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            精品综合久久久久久88小说| 亚洲国产天堂久久综合| 亚洲AV无码久久精品蜜桃| 亚洲色欲久久久综合网东京热 | 亚洲欧美日韩久久精品| 亚洲国产成人久久综合一区77| 国色天香久久久久久久小说| 国内精品久久人妻互换| 国产精品亚洲美女久久久| 久久国产免费直播| 亚洲天堂久久精品| 伊人久久大香线蕉av一区| 精品人妻伦一二三区久久| 久久久久AV综合网成人| 国产午夜精品久久久久九九| 中文字幕久久亚洲一区| 久久99国产精品99久久| 久久人人爽人人人人片av| 久久99精品国产99久久6| 精品久久久久久无码专区| 久久国产亚洲精品| AAA级久久久精品无码区| 久久久久久久久久久久中文字幕 | 国产精品久久久福利| 久久人做人爽一区二区三区| 精品久久久久久亚洲| 久久青青草原精品国产| 狠狠色丁香久久婷婷综合| 久久久久无码中| 久久国产精品一区| 99久久婷婷国产一区二区| 俺来也俺去啦久久综合网| 久久香蕉超碰97国产精品| 久久久久久久综合狠狠综合| 久久se这里只有精品| 久久国产精品一区| 欧美一级久久久久久久大| 欧美一区二区久久精品| 久久精品青青草原伊人| 亚洲中文字幕无码一久久区| 无码AV波多野结衣久久|