网络流入门6：牛选牛圈

< 网络流入门6：牛选牛圈

1120: [视频]网络流入门6：牛选牛圈

时间限制: 1 Sec   内存限制: 128 MB
提交: 72   解决: 26
[ 提交][ 状态][ 讨论版]

题目描述

【问题描述】
有N(1 <= N <= 1000) 头牛，B (1 <= B <= 20)个牛圈。
每头牛对于牛圈都有不同的喜好值(最喜欢为1，最不喜欢为B）。牛圈有一定的容量。
现在分配每头牛到牛圈去，要求所有牛的最大喜好值与最低喜好值的差值最小。输出最小的“喜好值差”。
【输入格式】
第一行N和B
下来N行，每行B个数。表示喜欢的牛圈的序号，按喜欢的程度（递减）给出，比如第一个给出的牛圈的就是最喜欢，最后一个就是最不喜欢的。 
下来B个数，每个数表示牛圈最多容纳的牛的数目。
【输出格式】
输出最小的“喜好值差”。
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

这一道题的建图如下：

由原点连接每一头牛，边的流量为1，这个不用说了

由牛棚连接终点，流量为牛棚的容量

但是为什么牛和牛棚之间没有边呢？

那是因为如果全部建一次很浪费内存和时间，所以只需要在二分判断时根据x值来建满足条件的边

代码：

#include<cstdio>
#include<cstring>
using namespace std;
struct node
{int x,y,c,next,other;
}a[210000];
int len,last[210000],st,ed;
inline void ins(int x,int y,int c)
{int k1,k2;len++;k1=len;a[len].x=x;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;len++;k2=len;a[len].x=y;a[len].y=x;a[len].c=0;a[len].next=last[y];last[y]=len;a[k1].other=k2;a[k2].other=k1;
}
int list[1100],head,tail,h[1100];
inline bool bt_h()
{memset(h,0,sizeof(h));h[st]=1;list[1]=st;head=1;tail=2;while(head!=tail){int x=list[head];for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(a[k].c>0 && h[y]==0){h[y]=h[x]+1;list[tail++]=y;}}head++;}if(h[ed]>0)return true;else return false;
}
inline int mymin(int x,int y)
{return x<y?x:y;
}
int findflow(int x,int f)
{if(x==ed)return f;int s=0,t;for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(a[k].c>0 && h[y]==(h[x]+1) && s<f){s+=(t=findflow(y,mymin(a[k].c,f-s)));a[k].c-=t;a[a[k].other].c+=t;}}if(s==0)h[x]=0;return s;
}
int n,m;
int b[1100][31],kk[1100];//b[i][j]表示第i头牛对j牛棚的喜欢程度，kk表示牛棚能容纳的牛的只数 
inline int check(int x)//表示这个“喜好值差”能 满足多少头牛 
{int i,j,ll,rr,s=0;st=n+m+1;ed=n+m+2;//for循环枚举头和尾//找自己第ll喜欢到第ll+x-1喜欢的牛棚//保证值≤x for(ll=1;ll<=m-x+1;ll++){rr=ll+x-1;len=0;memset(last,0,sizeof(last));for(i=1;i<=n;i++) ins(st,i,1);for(i=n+1;i<=n+m;i++) ins(i,ed,kk[i-n]);for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(b[i][j]>=ll && b[i][j]<=rr)//如果这个牛棚在ll和rr（查找范围）之间 ins(i,j+n,1);//就建立一条边 s=0;while(bt_h()==true) s+=findflow(st,999999999);//查找流量 if(s==n) break;//如果满足就不用再找了 }return s;
}
int main()
{int i,j,tt;scanf("%d%d",&n,&m);for(i=1;i<=n;i++)for(j=1;j<=m;j++){scanf("%d",&tt);b[i][tt]=j;}for(i=1;i<=m;i++) scanf("%d",&kk[i]);int l,r,mid,ans=0;l=0,r=m;while(l<=r){mid=(l+r)/2;if(check(mid)==n){r=mid-1;ans=mid;}else{l=mid+1;}}printf("%dn",ans);return 0;
}