description

一年一度的綜藝節(jié)目《中國新代碼》又開始了。Zayid 從小就夢想成為一名程序員，他覺得這是一個展示自己的舞臺，于是他毫不猶豫地報名了。

輕車熟路的 Zayid 順利地通過了海選，接下來的環(huán)節(jié)是導(dǎo)師盲選，這一階段的規(guī)則是這樣的：
總共 n名參賽選手（編號從 1 至 n）每人寫出一份代碼并介紹自己的夢想。接著由所有導(dǎo)師對這些選手進(jìn)行排名。為了避免后續(xù)的麻煩，規(guī)定不存在排名并列的情況。

同時，每名選手都將獨立地填寫一份志愿表，來對總共 m位導(dǎo)師（編號從 1 至 m）作出評價。志愿表上包含了共 m 檔志愿。對于每一檔志愿，選手被允許填寫最多 C位導(dǎo)師，每位導(dǎo)師最多被每位選手填寫一次（放棄某些導(dǎo)師也是被允許的）。

在雙方的工作都完成后，進(jìn)行錄取工作。每位導(dǎo)師都有自己戰(zhàn)隊的人數(shù)上限，這意味著可能有部分選手的較高志愿、甚至是全部志愿無法得到滿足。

節(jié)目組對 ‘‘前 i名的錄取結(jié)果最優(yōu)’’ 作出如下定義：
前 1名的錄取結(jié)果最優(yōu)，當(dāng)且僅當(dāng)?shù)?1 名被其最高非空志愿錄取（特別地，如果第 1名沒有填寫志愿表，那么該選手出局）。
前 i名的錄取結(jié)果最優(yōu)，當(dāng)且僅當(dāng)在前 i?1 名的錄取結(jié)果最優(yōu)的情況下：第 i 名被其理論可能的最高志愿錄取（特別地，如果第 i名沒有填寫志愿表、或其所有志愿中的導(dǎo)師戰(zhàn)隊均已員，那么該選手出局）。

如果一種方案滿足 ‘‘前 n名的錄取結(jié)果最優(yōu)’’，那么我們可以簡稱這種方案是最優(yōu)的。

舉例而言，2位導(dǎo)師 T 老師、F 老師的戰(zhàn)隊人數(shù)上限分別都是 1 人；2 位選手 Zayid、DuckD 分列第 1、2 名。那么下面 3種志愿表及其對應(yīng)的最優(yōu)錄取結(jié)果如表中所示：

可以證明，對于上面的志愿表，對應(yīng)的方案都是唯一的最優(yōu)錄取結(jié)果。
每個人都有一個自己的理想值 si，表示第 i 位同學(xué)希望自己被第 si或更高的志愿錄取，如果沒有，那么他就會非常沮喪。
現(xiàn)在，所有選手的志愿表和排名都已公示。巧合的是，每位選手的排名都恰好與它們的編號相同。
對于每一位選手，Zayid 都想知道下面兩個問題的答案：
在最優(yōu)的錄取方案中，他會被第幾志愿錄取。
在其他選手相對排名不變的情況下，至少上升多少名才能使得他不沮喪。
作為《中國新代碼》的實力派代碼手，Zayid 當(dāng)然輕松地解決了這個問題。不過他
還是想請你再算一遍，來檢驗自己計算的正確性。

輸入格式
每個測試點包含多組測試數(shù)據(jù)，第一行 2個用空格隔開的非負(fù)整數(shù) T,C，分別表示
數(shù)據(jù)組數(shù)、每檔志愿最多允許填寫的導(dǎo)師數(shù)目。

接下來依次描述每組數(shù)據(jù)，對于每組數(shù)據(jù)：
第 1行兩個用空格隔開的正整數(shù) n, m。
n, m分別表示選手的數(shù)量、導(dǎo)師的數(shù)量。

第 2行 m 個用空格隔開的正整數(shù)：其中第 i 個整數(shù)為 bi。
bi表示編號為 i 的導(dǎo)師戰(zhàn)隊人數(shù)的上限。

第 3行至第 n+2 行，每行 m 個用空格隔開的非負(fù)整數(shù)：其中第 i+2 行左起第 j 個數(shù)為 ai,j。
ai,j表示編號為 i 的選手將編號為 j 的導(dǎo)師編排在了第 ai,j 志愿。特別地，如果 ai,j=0，則表示該選手沒有將該導(dǎo)師填入志愿表。在這一部分，保證每行中不存在某一個正數(shù)出現(xiàn)超過 C次（0 可能出現(xiàn)超過 C 次），同時保證所有 ai,j≤m

第 n+3行 n 個用空格隔開的正整數(shù)，其中第 i 個整數(shù)為 si。
si表示編號為 i的選手的理想值。在這一部分，保證 si≤m

輸出格式
按順序輸出每組數(shù)據(jù)的答案。對于每組數(shù)據(jù)，輸出 2行：
第 1行輸出 n 個用空格隔開的正整數(shù)，其中第 i 個整數(shù)的意義為：
在最優(yōu)的錄取方案中，編號為 i的選手會被該檔志愿錄取。
特別地，如果該選手出局，則這個數(shù)為 m+1

第 2行輸出 n 個用空格隔開的非負(fù)整數(shù)，其中第 i 個整數(shù)的意義為：
使編號為 i的選手不沮喪，最少需要讓他上升的排名數(shù)。
特別地，如果該選手一定會沮喪，則這個數(shù)為 i

樣例 1

3 5 2 2 1 1 2 2 1 2 1 1 2 2 1 1 1 2 1 2 2 1 2 2 1 1 0 1 0 1 2 22 1 1 0 1 2 0 1 1 3 0 1

三組數(shù)據(jù)分別與「題目描述」中的三個表格對應(yīng)。

對于第 1組數(shù)據(jù)：由于選手 1 沒有填寫第一志愿，所以他一定無法被第一志愿錄
取，也就一定會沮喪。選手 2 按原排名就不沮喪，因此他不需要提升排名。
對于第 2 組和第 3 組數(shù)據(jù)：1 號選手都不需要提升排名。而希望被第一志愿錄取的 2 號選手都必須升到第 1名才能如愿

樣例 2

1 5 4 3 2 1 1 3 1 3 0 0 1 3 1 2 2 3 1 2 3 3 31 1 3 2 0 0 0 0

1號選手的第一志愿只填寫了 2 號導(dǎo)師，因此 1 號選手必定被 2 號導(dǎo)師錄取。
2 號選手的第一志愿只填寫了 3 號導(dǎo)師，因此 2 號選手必定被 3 號導(dǎo)師錄取。
由于 2,3 號導(dǎo)師均滿員，且 3,4 號選手均填寫了 1 號導(dǎo)師，因此它們都會被 1 號導(dǎo)師錄取。
所以 1,2 號選手均被第 1 志愿錄取，3 號選手被第 3 志愿錄取，4 號選手被第 2志愿錄取。
由于他們都如愿以償了，所以他們都不需要提升名次。

數(shù)據(jù)范圍與提示
對于所有測試點，保證 T≤5
對于所有測試點中的所有數(shù)據(jù)，保證 m≤n≤200，bi≤n。

solution

匈牙利的算法太( ??? )ﾉ了！！

直接暴力枚舉每個選手從優(yōu)到劣的志愿欄，然后嘗試與該志愿的某位導(dǎo)師配對
如果導(dǎo)師還有名額那么直接加入
滿額了，就讓枚舉該導(dǎo)師的所有學(xué)員全去嘗試能不能去選另外等價地位的導(dǎo)師
給這名選手騰個位置出來
過程用匈牙利可以跑
至于最少提升多少名次？？
很巧妙地，在跑匈牙利的時候，讓$x$改變匹配的導(dǎo)師時候，其實就意味著如果現(xiàn)在的選手代替$x$，他就能匹配到$x$現(xiàn)在匹配的導(dǎo)師
所以只需要求匈牙利過程中增廣的$x$編號的最大值
現(xiàn)在的選手編號減去最大值就是最少上升名次

code

#include <cstdio> #include <cstring> #include <iostream> using namespace std; #define maxn 205 int T, C, n, m, now, maxx; int lim[maxn], s[maxn], match[maxn], id[maxn], minn[maxn]; int tot[maxn][maxn];//tot[i][j] i選手的第j志愿一共填了多少導(dǎo)師 int wish[maxn][maxn][maxn];//wish[i][j][k] i選手的第j志愿欄選的第k位導(dǎo)師 bool vis[maxn];bool find( int u, int k ) {if( u < now ) maxx = max( maxx, u );for( int i = 1;i <= tot[u][k];i ++ ) {int v = wish[u][k][i]; //枚舉k支援欄i選手屬于的導(dǎo)師if( vis[v] ) continue;vis[v] = 1;if( lim[v] ) {//如果v導(dǎo)師還有名額 直接進(jìn)入 match[u] = v;id[u] = k;lim[v] --; return 1; } for( int j = 1;j <= n;j ++ ) {//枚舉v導(dǎo)師集合中的其他選手 看能不能換等地位的導(dǎo)師陣營 讓u成為v導(dǎo)師人員 if( j == u || match[j] != v ) continue;if( find( j, id[j] ) ) {match[u] = v;id[u] = k;return 1;}}}return 0; }int main() {scanf( "%d %d", &T, &C ); while( T -- ) {memset( tot, 0, sizeof( tot ) );memset( wish, 0, sizeof( wish ) );memset( match, 0, sizeof( match ) ); scanf( "%d %d", &n, &m );for( int i = 1;i <= m;i ++ )scanf( "%d", &lim[i] );for( int i = 1;i <= n;i ++ )for( int j = 1, rnk;j <= m;j ++ ) {scanf( "%d", &rnk );if( ! rnk ) continue;else wish[i][rnk][++ tot[i][rnk]] = j;}for( int i = 1;i <= n;i ++ )scanf( "%d", &s[i] );for( int i = 1;i <= n;i ++ )id[i] = m + 1, minn[i] = i;for( int i = 1;i <= n;i ++ ) {memset( vis, 0, sizeof( vis ) );now = i; for( int j = 1;j <= m;j ++ ) {if( ! tot[i][j] ) continue; //第j志愿欄為空 跳過maxx = 0;if( find( i, j ) ) { //i選手可以成為j志愿欄里某導(dǎo)師的學(xué)員 if( j <= s[i] ) minn[i] = 0;break;}if( j <= s[i] ) minn[i] = min( minn[i], i - maxx );}}for( int i = 1;i <= n;i ++ )printf( "%d ", id[i] );printf( "\n" );for( int i = 1;i <= n;i ++ )printf( "%d ", minn[i] );printf( "\n" );}return 0; }

總結(jié)

以上是生活随笔為你收集整理的[八省联考2018]劈配 （匈牙利）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。