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