表示很不解，这题我认为是求一般图匹配，于是未匹配数=n-匹配数*2，于是总的需要的就有n-匹配数*2+匹配数=n-匹配数。

但是这题大家都说是2分图，不过和原来做2分图的时候很不同，这题看了discuss说是建双向边，但是原来的2分图匹配都是只建单向边，从左边顶点集合指向右边顶点集合。

这样建图后我用匈牙利算法求解的时候，求得得匹配数是真正匹配数的两倍，这是否说明了一般图匹配都可以用2分图匹配做？？

表示严重不解。。。。

严重求教各位神牛！

• Re:这题不是一般图匹配么？为什么都说是2分图？？ (3) sepcity 2010-07-20 09:26:23
  • 毛。。九月祖师爷告诉我为什么啊 (12) NARUTOACM 2010-07-20 10:26:18