用最大流实现二部图最大匹配

　　为了某个已经折腾了两周的程序，花了两天时间实现了二部图的最大匹配，现分享如下。

　　题目的简化版是这样的：ABCD四个节点要对应1234四个节点，每个字母对应一个数字、每个数字对应一个字母。已知每个字母与每个数字只见的对应代价是不一样的。现在求最佳的配对方案，使得总代价最大／最小。
　　这个问题属于二部的带权匹配问题，网上似乎有不少解法，基本上是用匈牙利算法解决的。但是考虑到带权问题的复杂性，以及日后扩充要求的可能性，[tc]决定还是用网络流来求解。

　　[tc]的参考书：《网络最优化》，刘家壮，高等教育出版社，1991年。
　　用网络流求解的思路是这样的。由于已知字母与数字的关系如下图所示（对应关系的弧略去），
　　　A \/ 1
　　　B \/ 2
　　　C /\ 3
　　　D /\ 4
　　可以在现有的关系基础上，增加一个只有出度的开始节点s，和一个只有入度的结束节点t。
　　　　/　A \/ 1 \
　　　S -　B \/ 2 - T
　　　　\　C /\ 3 /
　　　　\　D /\ 4 /
　　显然s到t的计算过程可以找到字母与数字的匹配。现在设网络内的容量全部为1，当前流量为0，那么容易证明匹配结束后，每个字母对应一个数字、每个数字对应一个字母。

　　既然思路确定了，程序也就简单了。下面的代码是用来测试的，实际使用时可以整理成类，整理成类的方法就不说了。
　　注意这个算法的时间复杂度大约是O(n^2*L)，n是矩阵度数，L是一个不确定的值，L < n，与匈牙利算法的O(n ^ 3)相比差不多，但是可以轻易的扩展成更复杂的程序。
　　另外为了功能需要，下面的代码包括了求最大最小值两个代码，是用宏定义来区分的，看代码时请特别小心。


#include "stdafx.h"
//////////////////////////////////////////////////////////////////
// 用最大流实现二分图最大匹配
// 网络最大流（容量1），添加了超级源、超级汇
#include < stdio.h >
#include < string.h >
/*
样例：
INPUT
3

3 5 2
3 2 8
7 5 8

OUTPUT
20
*/

// 如果是寻最大值，需要下面这句
// 如果是寻最小值，屏蔽下面这句
//#define __FIND_MAX

const int maxn=100;
const int maxint=32767;
struct stuAbutMatrixNode // 邻接矩阵
{
int weight, // 权重
flux, // 流量
capability; // 容量
};

struct stuGraphicNode
{
int value, // 值
fa; // 度
};
stuAbutMatrixNode iAbility[maxn+2+1][maxn+2+1]; // 0..maxn+2
stuGraphicNode best[maxn+2+1];
int numItems,
numMaxWork,
s,t; // s、t是始边、终边的下标

void init()
{
int i,j;
scanf("%d",&numItems);
memset(iAbility,0,sizeof(iAbility));
for(i=1;i<=numItems;i++)
for(j=numItems+1;j<=2*numItems;j++)
{
iAbility[i][j].capability=1;
int iInput;
scanf("%d",&iInput);
iAbility[i][j].weight=iInput;
iAbility[j][i].weight=-iInput;
}
s=2*numItems+1;
t=2*numItems+2;
for (i=1;i<=numItems;i++)
{
iAbility[s][i].capability=1;
iAbility[numItems+i][t].capability=1;
}
numMaxWork=0;
}

bool find()
{
int i,j;
bool quit;
#ifdef __FIND_MAX
memset(best,0,sizeof(best));
best[s].value=1;
#else
for(i=1;i<=2*numItems+2;i++)
best[i].value=maxint;
best[s].value=0;
#endif
do
{
quit=true;
for(i=1;i<=2*numItems+2;i++)
#ifdef __FIND_MAX
if(best[i].value>0)
#else
if(best[i].value!=maxint)
#endif
for(j=1;j<=2*numItems+2;j++)
if (iAbility[i][j].flux
#ifdef __FIND_MAX
if (best[i].value+iAbility[i][j].weight>best[j].value)
#else
if (best[i].value+iAbility[i][j].weight
#endif
{
best[j].value=best[i].value+iAbility[i][j].weight;
best[j].fa=i;
quit=false;
}
}while(!quit);

#ifdef __FIND_MAX
if(best[t].value>1)
return true;
else
return false;
#else
if(best[t].value
return true;
else
return false;
#endif
}

void add()
{
int i,j;
i=t;
while(i!=s)
{
j=best[i].fa;
iAbility[j][i].flux++;
iAbility[i][j].flux=-iAbility[j][i].flux;
i=j;
}

int x,y,value;
y=best[t].fa;
x=best[y].fa;
value=iAbility[x][y].weight;
printf("(%d,%d)=%d\n",x,y-numItems,value);

#ifdef __FIND_MAX
numMaxWork+=best[t].value-1;
#else
numMaxWork+=best[t].value;
#endif
}

int main()
{
init();

while(find())
add();


#ifdef __FIND_MAX
printf("Max=%d\n",numMaxWork);
#else
printf("Min=%d\n",numMaxWork);
#endif

return 0;
}