http://www.cublog.cn/u3/113538/showart_2212681.html

http://hi.baidu.com/scaneelingg/blog/item/a639111e08b98ac2a7866992.html

总是想不到二分.学到了多重匹配,X中一个点可以匹配Y中多个点,但Y中的点只能匹配一个X中的点.做法貌似是匈牙利算法的变种.也可以用最大流来做多重匹配,每一个X中的点连S,容量为1,每一个牛棚连T,容量为牛棚容量,XY之间按二分上下限连,但效率貌似要低.

#include <cstdio>
#include <cstring>

#define maxn 1001
#define maxm 21
int n,m;
//bool map[maxn][maxm];
int map[maxn][maxm];
int match[maxm][maxn];
bool v[maxm];
int cap[maxm];

int c[maxm];
int l,r;

int dfs(int p)
{
    int i,j;
    for(i=1;i<=m;i++)
        //if(map[p][i] && !v[i])
        if(l<=map[p][i] && map[p][i]<=r && !v[i])
        {
            v[i]=1;
            if(cap[i])
            {
                --cap[i];
                match[i][ ++match[i][0] ]=p;
                return 1;
            }
            else
            {
                for(j=1;j<=match[i][0];j++)
                    if(dfs(match[i][j]))
                    {
                        match[i][j]=p;
                        return 1;
                    }
            }
        }
    return 0;
}

int maxmatch()
{
    int i,ans=0;
    for(i=1;i<=m;i++)
        match[i][0]=0;
    for(i=1;i<=n;i++)
    {
        memset(v,false,sizeof(v));
        ans+=dfs(i);
    }
    return ans;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int i,j,N,B,b;scanf("%d%d",&N,&B);
    for(i=1;i<=N;i++)
        for(j=1;j<=B;j++)
        {
            scanf("%d",&b);
            map[i][b]=j;
        }

    for(j=1;j<=B;j++)
        scanf("%d",&c[j]);

    l=r=1;
    int ans=B+1;
    while(l<=r && r<=B)
    {
        for(i=1;i<=B;i++) cap[i]=c[i];
        n=N;m=B;
        if(maxmatch()==N)
        {
            if(ans>r-l+1) ans=r-l+1;
            ++l;
        } else ++r;
    }
    printf("%d\n",ans);
}

话说从上次回来后就很久没做了,一直在忙落下的作业和实验,要坚持啊.