原题链接

题目大意

有n头牛和b个棚，每个棚有容量上限。每头牛心中对每个棚有个排名，现在给牛分配住棚且棚中牛的数目不能超过该棚的上限，求排名之间差的最小值。

输入格式

第1行输入n和b
第2~n+1行，每行b个数，第i行第j列表示第i-1头牛心目中排名是j的牛棚是a
第n+2行 有b个数，表示每个牛棚的容量上限

题目分析

首先一对多匹配问题，考虑扩展版匈牙利算法。
二分答案mid，枚举所有上长度为mid的区间求一对多匹配。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mkp(a,b) make_pair(a,b)
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1010,B=30;
int g[N][B],n,m;
int cnt[N];
struct node
{
    int id[N],k;
}match[B];
bool st[B];
bool find(int u,int low,int high)
{
    for(int i=1;i<=m;i++)
    {
        if(st[i]||g[u][i]<low||g[u][i]>high) continue;
        st[i]=1;
        if(match[i].k<cnt[i]) return match[i].id[++match[i].k]=u,1;
        for(int j=1;j<=cnt[i];j++)
            if(find(match[i].id[j],low,high)) return match[i].id[j]=u,1;
    }
    return 0;
}
bool check(int mid)
{
    for(int i=1;i<=m;i++)
    {
        bool ok=1;
        for(int j=1;j<=m;j++) match[j].k=0;
        for(int j=1;j<=n;j++)
        {
            memset(st,0,sizeof st);
            if(!find(j,i,min(m,i+mid-1))) 
            {
                ok=0;
                break;
            }
        }
        if(ok) return 1;
    } 
    return 0;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++) 
            {
                int a;
                scanf("%d",&a);
                g[i][a]=j;
            }
        for(int i=1;i<=n;i++) scanf("%d",&cnt[i]);
        int l=1,r=m;
        while(l<r)
        {
            int mid=l+r>>1;
            if(check(mid)) r=mid;
            else l=mid+1;
        }
        printf("%d\n",l);
    }
    return 0;
}

看错输入输出错了好长时间，记录下来www