TIOJ 1253. 砲打皮皮

第一次寫二分匹配

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
using namespace std;
typedef long long int int64;
vector<int> to[3000];
bool vis[3000];
int match[3000];
int Argu(int k){
 for(int lx = 0;lx < to[k].size();lx++){
  int ind = to[k][lx];
  if(vis[ind]) continue;
  vis[ind] = true;
  if(match[ind] == -1 or Argu(match[ind])){

   match[ind] = k;
   match[k] = ind;
   return 1;
  }
 }
 return 0;
}
int MaxBipartMatch(int n){
 int cnt = 0;
 memset(match, -1, sizeof(match));
 for(int lx = 0;lx < n;lx++){
  for(int lx = n;lx < 2*n;lx++)
   vis[lx] = false;
  cnt += Argu(lx);
 }
 return cnt;
}

int main()
{
 int n, k; int cc = 1;
 for(;;cc++){
  scanf("%d %d", &n, &k);
  if(n+k == 0) break;
  for(int lx = 0;lx < 2*n;lx++)
   to[lx].clear();
  for(int lx = 0;lx < k;lx++){
   int a, b;
   scanf("%d %d", &a, &b);
   a--, b--; b+=n;
   to[a].push_back(b);
   to[b].push_back(a);
  }
  printf("Case #%d:%d\n", cc, MaxBipartMatch(n));
 }
 return 0;
}