km算法可以用来求最优匹配，但是，它本身蕴含着复杂的数学原理，我暂时还不知道怎么理解，仅仅在此提一道非匹配应用。
题目：
争 夺
题目描述：
小Y和小P无聊的时候就喜欢玩游戏，但是每次小P都输给了小Y。终于有一天，你看不过去了，决定帮小P一把。
游戏是这样的，一个N*M的棋盘（保证n或m中，至少有一个为偶数）。相邻格子之间有一个给定的正整数权值。要你给这些格子填上一些值，使得相邻两个格子本身的权值之和，要大于等于他们之间给定的权值。并且要使得所有格子权值之和最小。
输入文件：
第一行一个数N，M。如题所述。(n,m<=100)
接下来N行，每行2*M个数，第I行，第2*j-1个数和第2*J个数分别描述第I行第J个格子连向下方格子的边的权值
和 连向右方格子的边的权值。（这样的读入纯粹为了方便、统一）。 (每个权值>=0 且
<=1000)
输出文件：
第一行一个数，表示最少的权值和。
接下来N行，每行M个数。这个矩阵就是你所填的方案。
样 例：
输入：
2 3
1 2 3 4 5 6
7 8 9 10 11 12
输出：
15
1 1 3
0 8 2
一看到<=,>=约束条件，我就想到差分约束或上下界网络流，因此陷入思维误区，一直没想到与km算法的联系，其实若是将矩阵黑白染色分作两个集合，每个格子的值作为顶标，便会得出一个式子lx[i]+ly[j]>=w[i,j]，与km算法的式子如出一辙，km算法也就是维护这个式子达到最优匹配，虽然题目与匹配毫无关系，但我们依然可以通过km算法解题。