過山車

Time Limit: 1000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 27666????Accepted Submission(s): 11950


Problem Description RPG girls今天和大家一起去游樂場玩，終于可以坐上夢寐以求的過山車了。可是，過山車的每一排只有兩個座位，而且還有條不成文的規矩，就是每個女生必須找個個男生做partner和她同坐。但是，每個女孩都有各自的想法，舉個例子把，Rabbit只愿意和XHD或PQK做partner，Grass只愿意和linle或LL做partner，PrincessSnow愿意和水域浪子或偽酷兒做partner。考慮到經費問題，boss劉決定只讓找到partner的人去坐過山車，其他的人，嘿嘿，就站在下面看著吧。聰明的Acmer，你可以幫忙算算最多有多少對組合可以坐上過山車嗎？
Input 輸入數據的第一行是三個整數K , M , N，分別表示可能的組合數目，女生的人數，男生的人數。0<K<=1000
1<=N 和M<=500.接下來的K行，每行有兩個數，分別表示女生Ai愿意和男生Bj做partner。最后一個0結束輸入。
Output 對于每組數據，輸出一個整數，表示可以坐上過山車的最多組合數。
Sample Input 6 3 3 1 1 1 2 1 3 2 1 2 3 3 1 0
Sample Output 3
Author PrincessSnow

解析：二分匹配，具體的算法詳細看二分匹配算法。覺得大多都是個模板的應用。

代碼：

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<cctype> #include<algorithm> #include<vector> #include<map> #include<list> #include<stack> #include<set> #include<queue> #include<bitset> using namespace std; int p[510][510],_map[510],v[510]; int k,w,m;int find(int x) {for(int i=1; i<=m; i++)//遍歷所有被選者 {if(!v[i]&&p[x][i])//如果 x對i有好感且在這一個遞歸選取階段沒有被選取（哪怕是暫時選取，新的遞歸可能會換） {v[i]=1;//標記被選取 if(!_map[i]||find(_map[i]))//如果被選者沒有歸屬或他的歸屬著可以調換（他的歸屬者可以選擇其它被選者） {_map[i]=x;//將歸屬定為 x return 1;}}}return 0; } int main() {while(~scanf("%d%d%d",&k,&w,&m),k){memset(p,0,sizeof(p));memset(_map,0,sizeof(_map));for(int i=1; i<=k; i++){int a,b;scanf("%d%d",&a,&b);p[a][b]=1;//表示 a希望與 b有關系}int sum=0;for(int i=1; i<=w; i++){memset(v,0,sizeof(v));if(find(i))sum++;//尋找和man的匹配者 }printf("%d\n",sum);}return 0; }

總結

以上是生活随笔為你收集整理的hdu-2063的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。