• <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 我們首先選擇一個點標記為1從1像另外5個點生成邊機5條邊。而要繼續生成邊的話就會出現2匹配,與題意不符。可以證明在這類生成邊中 n k
            符合(n-1)+(n-2)+……+(n-k+1)及等差數列也可以認為是C(n,k);
            2.  此類生成圖就是存在斷點,我們知道圖中無重邊,無自環所以一個N個點的簡單圖最大有才C(n,2)條邊。而從最大二分匹配中得知一個n點圖,最大會出現k匹配
            反向思維我們知道如果給出n k,當n>2*k我們可以選擇n中的2k個點構造一個子完全圖(存在斷點),然后生成的邊符合最大不超過k匹配。
            最后比較1和2兩類生成邊數,取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

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            精品久久久无码人妻中文字幕| 国产精品久久久久久搜索| 国产精品九九九久久九九| 免费观看久久精彩视频| 亚洲精品乱码久久久久久蜜桃 | 国产A级毛片久久久精品毛片| 久久99精品综合国产首页| 996久久国产精品线观看| 久久国产热这里只有精品| 亚洲精品成人网久久久久久| A狠狠久久蜜臀婷色中文网| 久久99国产精品久久99| 香蕉久久久久久狠狠色| 久久久久免费精品国产| 99久久做夜夜爱天天做精品| 久久九九亚洲精品| 亚洲国产精品无码久久久秋霞2 | 青青草原综合久久| 亚洲七七久久精品中文国产| 久久精品国产半推半就| 亚洲精品无码成人片久久| 久久久国产精华液| 久久精品一区二区国产| 亚洲精品无码久久久久久| 区亚洲欧美一级久久精品亚洲精品成人网久久久久 | 久久久久se色偷偷亚洲精品av| 国产精品禁18久久久夂久| 久久亚洲中文字幕精品一区| 久久精品国产亚洲AV嫖农村妇女| 久久不见久久见免费影院www日本| 久久久久无码精品国产| 久久亚洲精品无码观看不卡| 久久精品国产只有精品2020| 久久超乳爆乳中文字幕| 久久久久亚洲精品天堂| 久久中文骚妇内射| 久久精品中文騷妇女内射| 亚洲国产精品久久久天堂| 久久综合久久自在自线精品自| 久久99精品久久久久久动态图| 亚洲色大成网站www久久九|