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

            Description

            What is the maximum number of edges in an undirected graph G of n vertices that avoids a k-matching? Note that loops and parallel edges are not allowed in the graph.

            Input

            The input contains several test cases.
            For each test case, there is one line with two positive integers, n ≤ 1000 and k ≤ 1000.
            The input ends with two zeroes.

            Output

            For each test case output the maximum number of edges.

            Sample Input

            1000 1
            500 2
            0 0
            

            Sample Output

            0
            499
            圖論中的匹配問題!K邊匹配問題
            開始的時候一直考慮少了一種情況。。。。
            我的思路是:
            生成圖 因為是最大K匹配所以生成的圖有兩類;
            1.   圖中不存在斷點也就是說所有的點存在在一個連通分量里。例如
            6 2 我們首先選擇一個點標(biāo)記為1從1像另外5個點生成邊機(jī)5條邊。而要繼續(xù)生成邊的話就會出現(xiàn)2匹配,與題意不符。可以證明在這類生成邊中 n k
            符合(n-1)+(n-2)+……+(n-k+1)及等差數(shù)列也可以認(rèn)為是C(n,k);
            2.  此類生成圖就是存在斷點,我們知道圖中無重邊,無自環(huán)所以一個N個點的簡單圖最大有才C(n,2)條邊。而從最大二分匹配中得知一個n點圖,最大會出現(xiàn)k匹配
            反向思維我們知道如果給出n k,當(dāng)n>2*k我們可以選擇n中的2k個點構(gòu)造一個子完全圖(存在斷點),然后生成的邊符合最大不超過k匹配。
            最后比較1和2兩類生成邊數(shù),取max,極為本題答案!
            1  4518669(3)  xujiaming  132K  0MS  C++  280B 
            posted on 2008-12-28 15:49 KNIGHT 閱讀(455) 評論(0)  編輯 收藏 引用
            <2008年12月>
            30123456
            78910111213
            14151617181920
            21222324252627
            28293031123
            45678910

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            国产精品久久久久久久app| 久久精品国产亚洲AV香蕉| 久久久久亚洲AV无码观看| 婷婷久久五月天| 日本强好片久久久久久AAA| 99久久国产宗和精品1上映| 久久精品中文闷骚内射| 亚洲一区中文字幕久久| 久久一区二区三区99| 亚洲综合伊人久久综合| 久久精品国产秦先生| 久久这里有精品视频| 亚洲精品白浆高清久久久久久| 91精品国产综合久久精品| 国内精品伊人久久久久影院对白| 香蕉aa三级久久毛片| 精品免费久久久久久久| 久久久久97国产精华液好用吗| 久久久SS麻豆欧美国产日韩| 99久久免费国产特黄| 麻豆久久久9性大片| 久久99毛片免费观看不卡| 色悠久久久久久久综合网| 久久国产色AV免费观看| 亚洲国产成人久久一区久久| 91精品国产乱码久久久久久| 久久亚洲AV成人无码软件 | 国产精品免费久久久久影院 | 国产婷婷成人久久Av免费高清| 久久93精品国产91久久综合| 午夜天堂精品久久久久| 久久这里有精品视频| 国产亚洲精午夜久久久久久| 国产精品久久久久久福利69堂| A级毛片无码久久精品免费| 伊人久久综合热线大杳蕉下载| 日韩乱码人妻无码中文字幕久久| 亚洲伊人久久成综合人影院| 久久97久久97精品免视看秋霞| 热re99久久精品国产99热| 精品久久久久久国产潘金莲|