二分图匹配—匈牙利算法构图最大流.ppt

基本概念最大匹配匈牙利算法匈牙利算法匈牙利算法bool寻找从k出发的对应项出的可增广路
{
while(从邻接表中列举k能关联到顶点j)
{
if(j不在增广路上){

把j加入增广路;
if(j是未盖点或者从j的对应项出发有可增广路)
{
修改j的对应项为k;
则从k的对应项出有可增广路,返回true;
}
}
}
则从k的对应项出没有可增广路,返回false;
}匈牙利算法模板(详见POJ2239)intmain(){inti,j,p,q,t;while(scanf("%d",&n)!=EOF){
memset(map,0,sizeof(map));memset(match,-1,sizeof(match));for(i=1;i<=n;i++){scanf("%d",&t);for(j=0;j<t;j++){scanf("%d%d",&p,&q);map[i][(p-1)*12+q]=1;}}printf("%d\n",maxMah());}return0;HDOJ_1150任务安排图示：习题例4：HDOJ_1151AirRaidInput:Input:“空袭”示意图结论：变种3:二分图的最大独立集样本数据：0结论：构图最大流poj3281怎么构图呢？USACO4.2ThePerfectStall如下图所示方式构图，每条边的容量为1，则从source到sink最大流量就等于cow与stall的最大匹配