Liny_@NotePad

沉迷ACG中

Try

YOYO posted @ 2009年5月12日 18:25 in 【ICPC】解题报告 with tags Hopcroft 二分图匹配 , 1835 阅读

FJNU2067：http://acm.fjnu.edu.cn/show?problem_id=2067

囧 二分图匹配…… 比赛的时候没细看 完全卡在B上了 没做出来
现在看看好囧噢。套模版的时候因为模版从1开始我从0开始忘了改交了好多WA 囧。

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. #define MAXN 10005
  5. #define MAXM 105
  6.  
  7. int m,n;
  8. bool used[MAXN];
  9. int link[MAXN];
  10. bool map[MAXN][MAXM];
  11.  
  12. bool check(int t){
  13.         for(int i=0; i<m; i++){
  14.                 if(!used[i]&&map[t][i]){
  15.                         used[i] = true;
  16.                         if(link[i]==-1||check(link[i])){
  17.                                 link[i] = t;
  18.                                 return true;
  19.                         }
  20.                 }
  21.         }
  22.         return false;
  23. }
  24.  
  25. int Max(){
  26.         int ans = 0;
  27.         memset(link, -1, sizeof(link));
  28.         for(int i=0;i<n;i++){
  29.                 memset(used, false, sizeof(used));
  30.                 if(check(i)) ans++;
  31.         }
  32.         return ans;
  33. }
  34.  
  35. int main(){
  36.         int k;
  37.         while(cin>>k>>m){
  38.                 memset(map, false, sizeof(map));
  39.                 int i,j,h,t;
  40.                 int key[MAXM], st[MAXM];
  41.                 n = 0;
  42.                 for(i=0; i<k; i++){
  43.                         cin>>key[i];
  44.                         if(key[i]>m)key[i]=m;
  45.                         st[i] = n;
  46.                         n+=key[i];
  47.                 }
  48.                 for(i=0; i<k; i++){
  49.                         for(j=0; j<m; j++){
  50.                                 cin>>t;
  51.                                 if(t==1){
  52.                                         for(h=0; h<key[i]; h++){
  53.                                                 map[st[i]+h][j] = true;
  54.                                         }
  55.                                 }
  56.                         }
  57.                 }
  58.                 cout<<Max()<<endl;
  59.         }
  60.         return 0;
  61. }

 

  • 无匹配
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter