稳定的奶牛分配 && 二分图多重匹配+二分答案

题意：

　　农夫约翰有N(1<=N<=1000)只奶牛，每只奶牛住在B(1<=B<=20)个奶牛棚中的一个。当然，奶牛棚的容量有限。有些奶牛对它现在住的奶牛棚很满意，有些就不太满意了。
农夫约翰想要重新安排这些奶牛，使得奶牛的满意度尽可能相同，尽管有可能这意味者所有的奶牛都不喜欢新分配的奶牛棚。
每只奶牛都按顺序给出她喜欢的奶牛棚。在某个分配方案中，一只奶牛的满意度等于她对她的奶牛棚的评价等级。你的工作是找出一种分配方案使得没有奶牛棚超出 它的容量，而且奶牛给分配到的奶牛棚的评价等级的相对范围（即分配到的等级最高的奶牛棚和等级最低的奶牛棚之间的差值）尽可能的小。

SOL：

　　出题人语死早。。。看半天没有看懂“分配到的等级最高的奶牛棚和等级最低的奶牛棚之间的差值”是什么东西，而且看样例也不知道他是怎么搞的。光看此题是一个二分图多重匹配（因为不会打网络流于是就什么都往二分图上靠），这玩意儿貌似在WC上第一题想偏点分，然而考场上打炸了——多重匹配就是一个点可以与多个点匹配——当然是单向的，即Y集中的点能与X集中多个点匹配。那么我们只要记录每个点的容量，再将link改成二维的，然后在匹配的时候判断即可，若没到容量直接匹配，若容量已满则对已连接的每个点增广。最后在最外层套一个二分答案即可

　　因为坑爹的题意，我到现在都不知道要求的到底是什么。。贴个多重匹配的void好了

　　

bool match(int node,int s){
	for(int i=first[node];i!=-1;i=next[i])
	if (vis[node][e[i].to]){
		int t=e[i].to;
		if (num[t]<cap[t]) { 
			num[t]++; 
			link[t][0]++; 
			link[t][link[t][0]]=node; 
			vis[node][t]=false;
			return true;
		}
		FORP(j,1,link[t][0]) if (match(link[t][j],s)) {
			link[t][j]=node;
			vis[node][t]=false;
			return true;
		}
	}
	return false;
}