題目描述某學(xué)校要召開一個舞會。已知學(xué)校所有 n 名學(xué)生中有些學(xué)生曾經(jīng)互相跳過舞。當(dāng)然跳過舞的學(xué)生一定是一個男生和一個女生。在這個舞會上要求被邀請的學(xué)生中的任何一對男生和女生互相都不能跳過舞。求這個舞會最多能邀請多少個學(xué)生參加。輸入格式輸入的第一行是 n 和 m 。其中 n 是可選的學(xué)生的總數(shù) m 是已知跳過舞的學(xué)生的對數(shù) ( n≤1000 m≤2000 。然后有 m 行每行包括兩個非負(fù)整數(shù)表示這兩個編號的學(xué)生曾經(jīng)跳過舞。學(xué)生的編號從 0 號到 n?1 號。輸出格式輸出文件僅一行為一個數(shù)字即能夠邀請的最多的學(xué)生數(shù)。輸入輸出樣例輸入 #1復(fù)制運行8 6 0 2 2 3 3 5 1 4 1 6 3 1輸出 #1復(fù)制運行5輸入 #2復(fù)制運行20 5 5 2 4 3 18 17 0 11 13 3輸出 #2復(fù)制運行161. 題意轉(zhuǎn)換用一句話剝離題目的背景故事這道題本質(zhì)上是在求在一個節(jié)點數(shù)為 N、邊數(shù)為 M 且“陣營未明確標(biāo)明”的二分圖中求解其“最大獨立集”的大小。2. 思考過程與解題思路面對這道題第一直覺的暴力解法是什么面對“最多能邀請多少人參加”的子集選擇問題初學(xué)者的第一直覺往往是狀壓DP或DFS暴力回溯枚舉這 n 個人到底“邀請”還是“不邀請”然后檢查選出的人中是否存在跳過舞的組合。時間復(fù)雜度將高達(dá) O(2^N)?？紤]到本題數(shù)據(jù)范圍 n≤10002^1000 的運算量必然會引發(fā)嚴(yán)重的超時。如何一步步推導(dǎo)到正解洞察隱含的圖論性質(zhì)題目有一句極其強烈的暗示——“跳過舞的學(xué)生一定是一個男生和一個女生”。這意味著如果我們把學(xué)生看作節(jié)點跳過舞的關(guān)系看作邊那么所有的邊都只存在于不同性別的群體之間絕對不存在同性之間的邊。這完美契合了二分圖的定義抽象問題模型“被邀請的學(xué)生中的任何一對男生和女生互相都不能跳過舞”即要求我們選出的節(jié)點集合中任意兩個節(jié)點都沒有邊相連。在圖論中這被稱為求圖的最大獨立集。召喚二分圖核心定理在二分圖中有一個非常優(yōu)美的結(jié)論最大獨立集點數(shù) 圖的總節(jié)點數(shù) - 最小頂點覆蓋數(shù)而根據(jù)柯尼希定理K?nigs theorem我們又知道最小頂點覆蓋數(shù) 最大匹配數(shù)所以最多邀請人數(shù) 總?cè)藬?shù) N - 最大匹配數(shù)。填補戰(zhàn)術(shù)盲區(qū)染色法思路很完美但遇到了一個問題輸入數(shù)據(jù)并沒有告訴我們誰是男誰是女因此在跑匹配算法之前我們必須先使用DFS 染色法黑白染色把互相排斥的節(jié)點強行劃分到“左部”和“右部”。3. 算法設(shè)計與樣例推演核心算法與數(shù)據(jù)結(jié)構(gòu)二分圖染色DFS利用vis數(shù)組記錄顏色0 未染1 左部2 右部。遇到未染色的相鄰節(jié)點就染上相反的顏色。匈牙利算法利用基于 DFS 的增廣路算法求出左部和右部之間的最大匹配數(shù)。鄰接表vectorint vec1存儲學(xué)生之間無向的跳舞關(guān)系。手玩推演核心邏輯以樣例 1 為例總共 8 個點 (0~7)。給定的邊為 (0,2), (2,3), (3,5), (1,4), (1,6), (3,1)。染色劃分階段 從 0 開始 DFSvis[0]1。 順著邊染色0(1) → 2(2) → 3(1) → 5(2) 以及 3(1) → 1(2) → 4(1) 和 1(2) → 6(1)。 最終左部集合vecl {0, 3, 4, 6,7}右部集合vecr {2, 5, 1}7是孤立點。匈牙利匹配階段 遍歷左集合尋找匹配 0 匹配 2 (成功) ;3 匹配 5 (成功) ;4 匹配 1 (成功);6 匹配 1 (失敗1已被4占據(jù)且無法騰出位置);7 找匹配,因為沒有連線直接失。最大匹配數(shù)為 3。計算答案 最多邀請人數(shù) 總?cè)藬?shù) 8 - 最大匹配數(shù) 3 5 人。與樣例輸出完全一致。4. 時空復(fù)雜度分析時間復(fù)雜度染色階段遍歷全圖復(fù)雜度為 O(NM)。匈牙利算法階段外層循環(huán)最多 N 次每次 DFS 最壞遍歷 M 條邊復(fù)雜度為 O(N×M)。總時間復(fù)雜度為 O(N×M)。本題 N≤1000,M≤2000最大運算量約 2×10^6在 C 1 秒的時限內(nèi)飛速跑完?？臻g復(fù)雜度使用了多個大小為 2010 的一維數(shù)組和vector存圖?？臻g復(fù)雜度為 O(NM)內(nèi)存開銷極小約幾MB遠(yuǎn)低于題目要求的 125MB絕對不會 MLE。5. 坑點與易錯總結(jié)節(jié)點編號從 0 開始這是一大殺手習(xí)慣了從 1 開始編號的同學(xué)如果在初始化linked數(shù)組時默認(rèn)用 0會導(dǎo)致 0 號節(jié)點被誤認(rèn)為“尚未匹配”。必須嚴(yán)格使用memset(linked, -1, sizeof(linked))。圖不連通多個獨立社交圈人群中可能存在多個互不相交的關(guān)系網(wǎng)。如果在染色時只寫一句dfs(0, -1)會導(dǎo)致其他圈子的人未被分組。必須使用for循環(huán)遍歷判斷vis[i] 0來開啟多源染色。單向存邊還是雙向存邊在還沒染色前我們根本不知道誰是左部誰是右部因此讀入數(shù)據(jù)時必須雙向存邊。6. 代碼進(jìn)階與優(yōu)化剖析核心教學(xué)點審視下方我提供的代碼整體邏輯極其嚴(yán)密防坑意識絕佳尤其是對 0 編號和圖不連通的處理。但要成為金牌選手我們需要關(guān)注以下常數(shù)優(yōu)化高階技巧匈牙利算法的“時間戳”常數(shù)優(yōu)化斷崖式提速看我的hungary()函數(shù)外層每遍歷一個點v都要執(zhí)行一次memset(used, 0, sizeof(used))。這意味著如果左部有 1000 人就要把數(shù)組全盤擦除 1000 遍引入了 O(N^2) 的基礎(chǔ)常數(shù)開銷。優(yōu)化思維其實我們只需要把當(dāng)前的輪次標(biāo)記比如正在幫左邊的u找對象把u1作為timestamp加1是為了避開0傳進(jìn)dfs2(int u, int timestamp)。把內(nèi)部的判斷條件!used[v]升級為used[v] ! timestamp然后used[v] timestamp。效果舊輪次的標(biāo)記天然不會干擾新輪次外層的memset可直接刪除這會讓你的代碼在面對嚴(yán)苛?xí)r限時擁有更強的生存能力。7. 完整代碼//這道題也是要畫圖瞅瞅 //先左邊畫8個點0-7 右邊畫8個點0-7 然后不能一起來的就連線 //發(fā)現(xiàn)這樣好像不太對因為左邊和右邊的點其實是有重復(fù)的但是只要這個點左邊不選右邊也不應(yīng)該存在這個點的 //所以我們要想辦法把不能一起出現(xiàn)的點分成左邊一撥和右邊一撥染色法 dfs遍歷 //然后找出這個一批點最大匹配 然后總點數(shù)-最大匹配就是我們要求的能夠邀請的最多的學(xué)生數(shù)了 #include iostream #include vector #include cstring//memset要用 using namespace std; int n,m; vectorint vec1[2010];//存起始的不能互相跳舞的男女隊 int vis[2010];//vis[i]1代表i點被染色成1 vis[i]2 代表i點被染色成2 vis[i]0代表還沒有被染色 vectorint vecl;//存左邊的那撥點 vectorint vecr;//存右邊的那撥點 int used[2010];//標(biāo)記右邊的那撥點在本輪循環(huán)中是否被使用過 int linked[2010];//右邊的點所匹配的左邊的點 //x是這輪dfs的起點 fa為父節(jié)點防止重復(fù)訪問 void dfs(int x,int fa){ //遍歷所有與x有邊相連的點v for(int v:vec1[x]){ //避免重復(fù)訪問 if(vfa) continue; //如果v點還沒有被染色 if(vis[v]0){ //v與x不能是同一種顏色 if(vis[x]1) vis[v]2; else vis[v]1; //繼續(xù)遍歷 dfs(v,x); } } } //u為這一輪循環(huán)的左點 //【優(yōu)化】進(jìn)階可擴充為bool dfs2(int u,int timestamp) 用時間戳取代每次的memset bool dfs2(int u){ //遍歷所有與u有邊相連的右點 for(int v:vec1[u]){ //如果v點這一輪循環(huán)還沒有使用過 if(!used[v]){ //把v點標(biāo)記為使用過 used[v]1; //若v還匹配左點 或者匹配v的那個左點能找到新的匹配的右點 if(linked[v]-1 || dfs2(linked[v])){ linked[v]u; return true; } } } return false; } //匈牙利算法求最大匹配 int hungary(){ int idx0;//記錄最大匹配數(shù) //初始化右邊的所有點都沒有匹配左邊點值為-1 memset(linked,-1,sizeof(linked)); //接下來遍歷所有左點 for(int v:vecl){ //每一輪循環(huán)前要初始化所有右點都沒有使用過 // 【優(yōu)化】若使用時間戳優(yōu)化 這行memset即可省略 常數(shù)下降 memset(used,0,sizeof(used)); if(dfs2(v)) idx; } return idx; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinnm; //存圖 for(int i1;im;i){ int a,b;//a和b為互相跳過舞的男女生 cinab; //無向邊雙向存邊 vec1[a].push_back(b); vec1[b].push_back(a); } //染色 把不能一起去的學(xué)生分成兩撥 從0號學(xué)生開始進(jìn)行dfs //為了防止圖有多個聯(lián)通塊 需要開for循環(huán)遍歷每個沒有被染色的點 for(int i0;in;i){ //如果i點還沒有被染色 if(vis[i]0){ vis[i]1;//就把它染色為1 dfs(i,-1);//然后從i點開始dfs 起點沒有父節(jié)點設(shè)為-1 } } //接下來所有點已經(jīng)被分成了左右兩撥 for(int i0;in;i){ //顏色為1的存進(jìn)左邊那撥點 if(vis[i]1) vecl.push_back(i); //顏色為2的存進(jìn)右邊那撥點 else vecr.push_back(i); } //接下來進(jìn)行匈牙利算法 找最大匹配 //最大獨立集總點數(shù)-最大匹配數(shù) coutn-hungary(); return 0; }