2部グラフのマッチング

2008年のGoogle Code Jamをちょっとだけやった．

2部グラフのマッチングの応用があった．

模範回答（？）のコードが想像以上に短かった．

こんな感じ．

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define FILL(xs, x) memset(xs, x, sizeof((xs)))
const int M = 100, N = 100;
int m, n, ind, matchX[M][N], matchY[M][N], visited[M][N], count;
bool room[M][N];
bool dfs(int x, int y)
{
if (x < ) return true;
if (visited[x][y] == count) return false;
visited[x][y] = count;
for (int i = x-1; i <= x+1; i++)
for (int j = y-1; j <= y+1; j+=2)
if ( <= i && i < m &&  <= j && j < n && room[i][j])
if ( dfs(matchX[i][j], matchY[i][j]) )
{
matchX[i][j] = x; matchY[i][j] = y;
matchX[x][y] = i; matchY[x][y] = j;
return true;
}
return false;
}
int solve()
{
int ret = ; count = ;
FILL(matchX,-1); FILL(matchY,-1); FILL(visited,);
for (int i = ; i < m; i++)
for (int j = ; j < n; j++)
if (room[i][j])
{
ret++;
if (j%2==1)
{
count++;
if (dfs(i,j)) ret--;
}
}
return ret;
}
int main()
{
int testCase;
cin >> testCase;
for (int iCase = 1; iCase <= testCase; iCase++)
{
cin >> m >> n;
for (int i = ; i < m; i++)
for (int j = ; j < n; j++)
{
char c;
cin >> c;
room[i][j] = c == '.';
}
cout << "Case #" << iCase << ": " << solve() << endl;
}
return ;
}

無駄が無いコードになっている．再帰をつかって簡潔になっている．

2部グラフのマッチングはこういうふうに書ける，というのは常識なんでしょうか？