題目大意：有N(N<100,000)個(gè)人要去M(M<10)個(gè)星球，每個(gè)人只可以去一些星球，一個(gè)星球最多容納Ki個(gè)人。請(qǐng)問(wèn)是否所有人都可以選擇自己的星球
題目分析；直接建立二分圖模型，使用匈牙利算法。
匈牙利算法可以解決多重匹配，原理和二分圖最大匹配很像。注意不要把可以匹配多個(gè)的點(diǎn)分割然后按照正常的二分匹配來(lái)做，那樣肯定會(huì)掛的。
解決多重匹配就是記錄一下多重匹配的點(diǎn)(簡(jiǎn)稱Y方點(diǎn))已經(jīng)匹配了Pi個(gè)點(diǎn)。如果Pi<Ki那么就直接上了，否則的話繼續(xù)搜索Yi已經(jīng)匹配的每一個(gè)點(diǎn)并將Yi染色。
因?yàn)閅i搜一次就需要染色了，而且Y方點(diǎn)最多是10個(gè)，所以每次找增廣路的深度最多是10，這樣就很快了。
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 100010;
const int maxm = 11;
int y_match[maxn][maxm], g[maxn][maxm], cnt[maxm], capacity[maxn], n, m;
bool vis[maxm];
bool dfs(int x) {
for(int i=0;i<m;i++) {
if(g[x][i] == 0 || vis[i] == true) continue;
vis[i] = true;
if(cnt[i] < capacity[i]) {
y_match[x][cnt[i]++] = x;
return true;
} else {
for(int j=0;j<capacity[i];j++) {
if(dfs(y_match[i][j]) == true) {
y_match[i][j] = x;
return true;
}
}
}
}
return false;
}
bool hungary(int n) {
for(int i=0;i<n;i++) {
memset(vis, false, sizeof(bool)*(m));
if(dfs(i) == false)
return false;
}
return true;
}
int main() {
while(~scanf("%d%d" , &n, &m)) {
memset(cnt, 0, sizeof(int)*(n));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d", &g[i][j]);
for(int i=0;i<m;i++)
scanf("%d", &capacity[i]);
if(hungary(n) == true)
puts("YES");
else
puts("NO");
}
return 0;
}
posted on 2015-02-13 16:23
JulyRina 閱讀(1442)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
解題報(bào)告