二分图匹配（指派问题）

本文主要是介绍二分图匹配（指派问题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

指派问题：

有N台计算机和K个任务，我们可以给每台计算机分配一个任务，每台计算机能够处理的任务种类不同，请求出最多能够处理的任务的个数。

思路：二分图匹配，可以这样来定义无向二分图，G=（UuV,E）;

U 代表计算机的顶点集合，V代表任务的顶点集合，对于任意u属于U和v属于V，计算机u能够处理的任务v<=>(u,v)属于E

二分图例子：

对原图做如下改变：

将原图中所有无向边e改为有向边，方向从U到V，容量1，增加源点s和汇点t,从s向所有的顶点u属于U连一条容量为1的边，从所有的顶点V属于V向t连一条容量1的边。

如此变形得到的新图G‘中最大的s-t流的流量就是原二分图中G的最大匹配，而U-V 之间的流量为正的边集合就是最大匹配，算法复杂度：O(|V||E|)。

代码实现：

int N,K,i,j;
bool can[maxn][maxn];            //  can[i][j] 表示计算机i 能处理任务j.    
void solve()
{// 0~N-1 :  计算机对应的顶点// N~N+K-1 : 任务对应的顶点int source=N+K,sink=s+1;for(int i=0; i<N; i++)      //源点和计算机之间连边add_edge(source,i,1);for(int i=0; i<K; i++)      //任务和汇点之间连边add_edge(N+i,sink,1);for(int i=0; i<N; i++)      //计算机和任务直接连边{for(int j=0; j<K; j++)if(can[i][j]){add_edge(i,N+j,1);}}printf("%d\n",max_flow(source,sink));
}