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