題意:給n(n<=26)張幻燈片,每張上面都有一個數字。給出所有幻燈片的位置和數字的位置,問哪些幻燈片上的數字可以確定。
解法:首先,如果給的合法的話,匈牙利算出來的一定是完全匹配的(也就是說,第一遍二分匹配算出來的一定是完全匹配)。然後再嘗試刪掉每一條完全匹配中的邊,如果刪掉後不能完全匹配,則說明這條邊是必須的,所以就確定了這個匹配並輸出。如果算出的完全匹配中沒有一個匹配是必須的,就輸出none好了。
代碼:
/******************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include
#include
#include
#include
#include
#include
#include
#include
#include