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