初涉二分图的最大权匹配 KM算法

这也是一道利用了DFS的题目，先说下我的思路：用一个二维数组记录每个字母所代表的含义（管道方向），用另一个二维数组记录4个方向的变换坐标；随后利用经典的DFS递归遍历即可~（还要注意在方向的处理上前后要保持一致，否则很容易计算出错 ：| ）

农田灌溉(Farm Irrigation)   

Benny有一大片农田需要灌溉。农田是一个长方形，被分割成许多小的正方形。每个正方形中都安装了水管。不同的正方形农田中可能安装了不同的水管。一共有11种水管，分别用字母A～K标明，如图1所示。 

则农田中水管分布如图2所示。 

样例输入：  

2 2

DK

HF

3 3

ADC

FJK

IHE

-1 -1

样例输出： 

2 3

闲话少叙，直接上代码+注释~

Code：

#include<iostream>
using namespace std;

#define MAXN 50
char map[MAXN][MAXN];	//地图
int M, N;				//M:农田行数，N:每行的正方形个数

int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };	//管道坐标变换的四个方向：对应的顺序上下左右。
int dirO[11][4] = {
	{-1, 0, -1, 0}, {-1, 0, 0, 1}, {0, 1, -1, 0},
	{0, 1, 0, 1}, {-1, 1, 0, 0}, {0, 0, -1, 1},
	{-1, 0, -1, 1}, {-1, 1, -1, 0}, {0, 1, -1, 1},
	{-1, 1, 0, 1}, {-1, 1, -1, 1}
	};		//每种农田块对应的4个管道方向(-1为左或上、1为右或下、0为没有)。

void DFS(int x, int y)
{
	int xx, yy;
	char temp = map[x][y];		//暂存当前农田块的形状，便于后面的比较~
	map[x][y] = ‘Y‘;			//覆盖原来农田为已遍历
	for(int i = 0; i < 4; i++)
	{
		//计算下一个方向的坐标。
		xx = x + dir[i][0];		
		yy = y + dir[i][1];
		if(xx<0 || xx>=MAXN || yy<0 || yy>=MAXN) continue;		//越界,跳至下一个方向的判断
		
		//方向所代表的值：上0、下1、左2、右3。
	
		//如果向上走(0)或向左走(2)，比如向左走则判断原坐标的“左”管道和下一个方向坐标的“右”管道，方向所代表的值+1
		if(i == 0 || i == 2)	
		{//若相邻两块农田管道能“接上”，即管道方向对应的值之积为-1
			if(map[xx][yy]!=‘Y‘ && dirO[temp-‘A‘][i]*dirO[map[xx][yy]-‘A‘][i+1]==-1) DFS(xx, yy);
		}
		//否则为向下走(1)或向右走(3)，比如向下走则判断原坐标的“下”管道和下一个方向坐标的“上”管道。对应方向所代表的值-1
		else if(map[xx][yy]!=‘Y‘ && dirO[temp-‘A‘][i]*dirO[map[xx][yy]-‘A‘][i-1]==-1) DFS(xx, yy);
	}
}
int main()
{
	int i, j;
	int count;
	while(scanf("%d%d", &M, &N))
	{
		count = 0;
		if(M < 0 || N < 0) break;
		for(i = 0; i < M; i++) scanf("%s", map[i]);			//以行为单位为map地图赋值
		//遍历地图、递归计数
		for(i = 0; i < M; i++)					
			for(j = 0; j < N; j++)
				if(map[i][j] != ‘Y‘) { DFS(i, j); count++; }
		printf("%d\n", count);
	}
	return 0;
}

如有Bug，欢迎拍砖~ ：）

初涉二分图的最大权匹配 KM算法,布布扣,bubuko.com

初涉二分图的最大权匹配 KM算法

原文：http://blog.csdn.net/zmx354/article/details/22762571