我就不贴题了，参见： http://acm.nankai.edu.cn/p2121.html

不带任何变化的、赤裸裸的二分图匹配问题。通过添加源和汇，可以转换成网络流问题。

今天学习了更加针对二分图匹配问题的匈牙利算法，又写了一遍这道题。

这个算法，原理不怎么好懂。可以参考：百度百科 郭嘉宝神牛的博客 和各种网络资源。

匈牙利算法程序非常好写，背下来也蛮容易的：

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

int map[101][101], mat[101];
bool b[101];

bool path (const int wh)
{
	int i;
	for (i=1; i<=map[wh][0]; i++)
#define VT map[wh][i]
		if (!b[VT])
		{
			b[VT] = true;
			if (mat[VT]==0 || path(mat[VT]))
			{
				mat[VT] = wh;
				mat[wh] = VT;
				return true;
			}
		}
	return false;
}

int main (void)
{
	FILE *fin = fopen("pilot.in", "r"),
		 *fout = fopen("pilot.out", "w");
	int M, N;

	fscanf(fin, "%d%d", &M, &N);
	while (1)
	{
		int a, b;
		fscanf(fin, "%d%d", &a, &b);
		if (a==-1)
			break;
		map[a][++map[a][0]] = b;
	}

	//匈牙利算法
	int i, match=0;
	for (i=1; i<=M; i++)
	{
		memset(b, 0, sizeof(bool)*(M+N));
		if (path(i))
			match++;
	}

	fprintf(fout, "%d\n", match);

	for (i=1; i<=M; i++)
		if (mat[i])
			fprintf(fout, "%d %d\n", i, mat[i]);

	fclose(fin);
	fclose(fout);

	return 0;
}