題目 1921:
藍(lán)橋杯算法提高VIP-金陵十三釵
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 827 解決: 179
題目描述
在電影《金陵十三釵》中有十二個(gè)秦淮河的女人要自我犧牲代替十二個(gè)女學(xué)生去赴日本人的死亡宴會(huì)。為了不讓日本人發(fā)現(xiàn)，自然需要一番喬裝打扮。但由于天生材質(zhì)的原因，每個(gè)人和每個(gè)人之間的相似度是不同的。由于我們這是編程題，因此情況就變成了金陵n釵。給出n個(gè)女人和n個(gè)學(xué)生的相似度矩陣，求她們之間的匹配所能獲得的最大相似度。
所謂相似度矩陣是一個(gè)n*n的二維數(shù)組like[i][j]。其中i,j分別為女人的編號(hào)和學(xué)生的編號(hào)，皆從0到n-1編號(hào)。like[i][j]是一個(gè)0到100的整數(shù)值，表示第i個(gè)女人和第j個(gè)學(xué)生的相似度，值越大相似度越大，比如0表示完全不相似，100表示百分之百一樣。每個(gè)女人都需要找一個(gè)自己代替的女學(xué)生。
最終要使兩邊一一配對(duì)，形成一個(gè)匹配。請(qǐng)編程找到一種匹配方案，使各對(duì)女人和女學(xué)生之間的相似度之和最大。
輸入格式
第一行一個(gè)正整數(shù)n表示有n個(gè)秦淮河女人和n個(gè)女學(xué)生
接下來(lái)n行給出相似度，每行n個(gè)0到100的整數(shù)，依次對(duì)應(yīng)二維矩陣的n行n列。
輸出格式
僅一行，一個(gè)整數(shù)，表示可獲得的最大相似度。
樣例輸入
4
97 91 68 14
8 33 27 92
36 32 98 53
73 7 17 82
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點(diǎn)擊這里了解課程詳情
標(biāo)簽