poj 3189 Steady Cow Assignment 二分图多重匹配

题意：

有n头牛和B个栏，每头牛i对每个栏j有喜爱程度rank[i][j]，每个栏i有容量cap[i],现在要把牛赶到栏里，在保证每个栏内的牛数量不超过容量的情况下，求所有牛中最大喜爱程度和最小喜爱程度差值的最小值。

思路：

枚举所有牛的最大喜爱程度high和最小喜爱程度low,对牛的集合和栏的集合进行二分图多重匹配(一个栏可以对应多头牛)。

代码：

//poj 3189
//sepNINE
#include <iostream>
using namespace std;
const int maxN=1024;
const int maxB=32;
int N,B,low,high;
int rank[maxN][maxB];
int match[maxB][maxN];
int vis[maxB];
int cap[maxB];int dfs(int x)
{int i,j;for(i=1;i<=B;++i){if(vis[i]==0&&rank[x][i]>=low&&rank[x][i]<=high){vis[i]=1;if(match[i][0]<cap[i]){match[i][++match[i][0]]=x;return 1;}else{for(j=1;j<=match[i][0];++j)if(dfs(match[i][j])==1){match[i][j]=x;return 1;	}			}	}			}return 0;
}
int mulmatch()
{int i,j;for(i=1;i<=B;++i)match[i][0]=0;for(i=1;i<=N;++i){memset(vis,0,sizeof(vis));if(dfs(i)==0)return 0;}return 1;	
}int main()
{scanf("%d%d",&N,&B);int i,j,x;for(i=1;i<=N;++i)for(j=1;j<=B;++j){scanf("%d",&x);rank[i][x]=j;}for(i=1;i<=B;++i)scanf("%d",&cap[i]);int ans=INT_MAX;low=high=1;while(low<=high&&high<=B){if(mulmatch()==1){ans=min(ans,high-low+1);++low;}else++high;}printf("%d",ans);		return 0;	
}