題目描述：
有N(N<100,000)個(gè)人要去M(M<10)個(gè)星球，每個(gè)人只可以去一些星球，一個(gè)星球最多容納Ki個(gè)人。請(qǐng)問(wèn)是否所有人都可以選擇自己的星球...
吐槽：
1. 雖然是水題，但是測(cè)試了一下dinic和匈牙利算法解決多重匹配的效率，還是值得紀(jì)念一下的....
2. hdu上需要用C++交.... 否則會(huì)因?yàn)樽x入超時(shí)... (害得我對(duì)拍+換算法搞了好久，否則昨天就捉好了.... )
算法分析：
直接建立二分圖模型，上匈牙利算法....
匈牙利算法可以解決多重匹配.... 注意不能把可以匹配多個(gè)的點(diǎn)分割然后按照正常的二分匹配來(lái)做，那樣肯定會(huì)掛的....
解決多重匹配就是記錄一下多重匹配的點(diǎn)(簡(jiǎn)稱(chēng)Y方點(diǎn))已經(jīng)匹配了Pi個(gè)點(diǎn)。如果Pi<Ki那么就直接上了，否則的話(huà)繼續(xù)搜索Yi已經(jīng)匹配的每一個(gè)點(diǎn)并將Yi染色...
因?yàn)閅i搜一次就需要染色了，而且Y方點(diǎn)最多是10個(gè)，所以每次找增廣路的深度最多是10... 這樣就很快了...
最大的一組數(shù)據(jù)100ms， 用dinic直接沒(méi)有結(jié)果(等的不耐煩了直接ctrl+c了)........
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 #define re(i,n) for(int i=0;i<n;i++)
5 const int N = 100005;
6 const int M = 11;
7 int yM[M][N];
8 int tem[M],num[M],chk[M];
9 int G[N][M];
10 int n,m;
11 bool dfs(int u){
12 re(v,m) if(G[u][v] && !chk[v]){
13 chk[v] =1;
14 if(tem[v] < num[v]){
15 yM[v][tem[v]++] = u;
16 return 1;
17 }
18 else re(i,tem[v])
19 if(dfs(yM[v][i])){
20 yM[v][i] = u;
21 return 1;
22 }
23 }
24 return 0;
25 }
26 int main(){
27 while(~scanf("%d%d",&n,&m)){
28 re(i,n) re(j,m) scanf("%d",&G[i][j]);
29 re(i,m) scanf("%d",&num[i]);
30 re(i,m) tem[i] = 0;
31 int flag = 1;
32 re(i,n) {
33 re(j,m) chk[j] = 0;
34 if(!dfs(i)) { flag = 0; break;}
35 }
36 puts(flag?"YES":"NO");
37 }
38 }
39
posted on 2012-05-06 14:20
西月弦 閱讀(1545)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
解題報(bào)告