hdu4685 最大比對可能性

題意:

      給你n個王子和m個公主,每個王子可以和自己喜歡的公主結婚,問你在不影響最大比對的前提下每個王子都可以去哪些公主.

思路:

      所有王子向他喜歡的公主連一條邊,然後比對一遍,之後再每個比對的公主連一條指向娶她的王子一條邊,然後對于那些光棍王子和單身公主們,其實他們可以和任意他們喜歡的人比對,因為可以讓自己幸福,然後拆散一對别人已經比對好的,雖然不道德,但是仍然滿足總的最大比對數不變,是以對于每一個光棍男我們就給他虛拟出一個女朋友,所有人都喜歡這個女的,但是這個女的隻喜歡并且和該光棍男比對,女的也類似這樣弄,最後每個人都有比對的對象了,此時我們隻要跑一遍強連通,同一個強連通分量裡的男和女可以随意比對..