牛棚安排
(Description)
Farmer John的N(1<=N<=1000)头奶牛分别居住在农场所拥有的B(1<=B<=20)个牛棚的某一个里。有些奶牛很喜欢她们当前住的牛棚，而另一些则讨厌再在它们现在所在的牛棚呆下去。
FJ在忍受了若干次奶牛的抱怨后，决定为所有奶牛重新安排牛棚，使最不满的那头奶牛与最高兴的奶牛的心情差异最小，即使这会让所有奶牛都更加郁闷。
每头奶牛都把她对各个牛棚的好感度从高到低排序后告诉了FJ。当然，如果一头奶牛被安排到的牛棚在她给出的列表中越靠后，她就会越郁闷。你可以认为奶牛的郁闷指数是她被分配到的牛棚在列表中的位置。奶牛们是斤斤计较的，她们无法容忍别的奶牛在自己喜欢的牛棚里快乐地生活，而自己却呆在一个自己不喜欢的牛棚里。每个牛棚都只能容纳一定数量的奶牛。FJ希望在每个牛棚都没有超出容量限制的前提下，使最郁闷和最高兴的奶牛的郁闷指数的跨度最小。
FJ请你帮他写个程序，来计算这个最小的郁闷指数跨度到底是多少。
(Input)
第1行: 包含2个用空格隔开的整数N和B，分别表示牛和牛棚的数量
第2..N+1行: 每行包含B个用空格隔开的整数，刚好完全包含1..B的整数。第i+1行的第一个整数，表示奶牛i最喜欢的牛棚编号。第二个整数表示奶牛i的列表中排在第二位，也就是她第二喜欢的牛棚。依此类推。
第N+2行: 包含B个用空格隔开的整数，第i个整数表示牛棚i最多能容纳的奶牛的数目。所有牛棚能容纳奶牛头数的和至少是N。
(Output)
第1行: 输出一个整数，表示所有奶牛中最高兴与最郁闷的牛的郁闷指数跨度
(Sample Input)
6 4
1 2 3 4
2 3 1 4
4 2 3 1
3 1 2 4
1 3 4 2
1 4 2 3
2 1 3 2
(Sample Output)
2
思路
我刚看到这题时，没有头绪，只能打表
比赛后，看了题解，秒懂！！！
最大流+二分
解析
题目要求使最郁闷和最高兴的奶牛的郁闷指数的跨度最小，我们不妨暴力枚举最高兴的，二分指数的跨度。
做完这些，可以考虑网络流。
源点： (N) 头牛，建一个超级源点连向每一个源点，流量为 (1) .
汇点： (B) 个牛棚，建一个超级汇点连向每一个汇点，流量为 牛棚能装下的牛的个数 .
再把 (N) 头牛连向在最郁闷和最高兴的范围（枚举的）中可以去的牛棚
最后跑一遍最大流就可以 (AC) 了
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int tot=1,n,m,a[1005][1005],b[10005],d[10005],q[10005],h[100005],cur[100005];
struct edge{
int to,nxt,z;
}e[500000];
void add(int x,int y,int z)
{
e[++tot].to=y;
e[tot].nxt=h[x];
e[tot].z=z;
h[x]=tot;
}
void build(int x,int y)
{
tot=1;
memset(h,0,sizeof(h));
for (int i=1;i<=n;i++) add(0,i,1),add(i,0,0);
for (int i=1;i<=n;i++)
for (int j=x;j<=y;j++)
add(i,a[i][j]+n,1),add(a[i][j]+n,i,0);
for (int i=1;i<=m;i++) add(n+i,n+n+1,b[i]),add(n+n+1,n+i,0);
}
bool bfs(int u)
{
for(int i=0;i<=n+n+n;i++) cur[i]=h[i];
memset(d,0,sizeof(d));
memset(q,0,sizeof(q));
int head=0,tail=0;
d[u]=1;
q[++tail]=u;
while (head<tail)
{
head++;
for (int i=h[q[head]];i;i=e[i].nxt)
{
int v=e[i].to;
if (d[v]!=0||e[i].z<=0) continue;
d[v]=d[q[head]]+1;
q[++tail]=v;
}
}
if (d[n+n+1]>0) return true;
else return false;
}
int dinic(int u,int mn,int fa)
{
if (u==n+n+1||mn==0) return mn;
int sum=0,flow=0;
for (int i=cur[u];i;i=e[i].nxt)
{
cur[u]=i;//本代码加入了当前弧优化
int v=e[i].to;
if (v==fa||d[v]!=d[u]+1||e[i].z<=0) continue;
sum=dinic(v,min(mn,e[i].z),u);
if (sum<=0) continue;
flow+=sum;
mn-=sum;
e[i].z-=sum;
e[i^1].z+=sum;
if (mn<=0) break;
}
return flow;
}
bool opt()
{
int res=0;
while (bfs(0)==true)
res+=dinic(0,2147483647,0);
if (res==n) return true;
else return false;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for (int i=1;i<=m;i++)
scanf("%d",&b[i]);
int ans=2147483647;
for (int i=1;i<=m;i++)
{
int l=0,r=m-i;
while(l<=r)
{
int mid=(l+r)>>1;
build(i,i+mid);
if (opt()==true) ans=min(ans,mid+1),r=mid-1;
else l=mid+1;
}
}
printf("%d
",ans);
}