我一眼费用流，等等不太对，感觉还是最大流好点。
题目描述
给你一堆奶牛和牛棚，每个奶牛可以匹配多个牛棚，而每个奶牛对每个牛棚之间的满意度是不一样的，并且每个牛棚的容量也是不一样的，问你最终可以有多少个牛匹配的牛棚满意度之和最小。
具体思路
首先，源点与每个奶牛之间连一条流量为 \(1\) 的边。
要满足每个牛棚的容量为 \(w_i\)，就在每个牛棚与汇点之间连一条容量为 \(w_i\) 的边。
显然不能每头奶牛和牛棚之间都连一条边。
我们考虑二分答案，设答案为 \(x\)。
然后枚举满意度 \(i\in [1,m-x+1]\)。
每次二分，每一头奶牛都与自己合法满意度的牛棚连边，然后跑一遍最大流，如果最大流跑出来的结果是 \(n\)，说明满足条件，此时的 \(x\) 就是答案。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=111000,M=1100;
const int inf=0x3f3f3f3f;
struct edge{int x,y,f,pre;}a[N];
int last[N],alen;
void ins(int x,int y,int f){
a[++alen]=edge{x,y,f,last[x]};
last[x]=alen;
a[++alen]=edge{y,x,0,last[y]};
last[y]=alen;
}
int n,m,w[N],s[M][M],ans;
int st,ed,h[N],cur[N];
bool bfs(){
memset(h,0,sizeof(h));h[st]=1;
queue<int>Q;Q.push(st);
while(!Q.empty()){
int x=Q.front();Q.pop();
for(int k=last[x];k;k=a[k].pre){
int y=a[k].y;
if(a[k].f&&!h[y]){
h[y]=h[x]+1;
Q.push(y);
}
}
}
return h[ed];
}
int dinic(int x,int f){
if(x==ed)return f;
int sx=0;
for(int k=cur[x];k;k=a[k].pre){
cur[x]=k;
int y=a[k].y;
if(a[k].f&&sx<f&&h[y]==h[x]+1){
int sy=dinic(y,min(f-sx,a[k].f));
a[k].f-=sy,a[k^1].f+=sy;
sx+=sy;
}
}
if(!sx)h[x]=0;
return sx;
}
int solve(){
ans=0;
while(bfs()){
memcpy(cur,last,sizeof(last));
ans=ans+dinic(st,inf);
}
return ans;
}
bool check(int x){
for(int i=1;i+x-1<=m;i++){
alen=1;memset(last,0,sizeof(last));
st=0,ed=n+m+1;
for(int j=1;j<=n;j++){
ins(st,j,1);
}
for(int j=1;j<=m;j++){
ins(n+j,ed,w[j]);
}
for(int j=1;j<=n;j++)
for(int k=i;k<=i+x-1;k++)
ins(j,n+s[j][k],1);
if(solve()==n)return true;
}
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",&s[i][j]);
for(int i=1;i<=m;i++){
scanf("%d",&w[i]);
}
int l=1,r=m,res;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){
r=mid-1;
res=mid;
}
else l=mid+1;
}
printf("%d",res);
return 0;
}