《算法周练3》E

二分图的多重匹配问题
解法:
1.带限制的匈牙利算法.
对匈牙利做一点调整就行了.
Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 2505;
const int M = 10000;
#define pi acos(-1)
#define INF 1e8
#define INM INT_MIN
#define pb(a)  push_back(a)
#define mk(a,b) make_pair(a,b)
#define dbg(x) cout << "now this num is " << x << endl;
#define met0(axx) memset(axx,0,sizeof(axx));
#define metf(axx) memset(axx,-1,sizeof(axx));
#define sd(ax) scanf("%d",&ax)
#define sld(ax) scanf("%lld",&ax)
#define sldd(ax,bx) scanf("%lld %lld",&ax,&bx)
#define sdd(ax,bx) scanf("%d %d",&ax,&bx)
#define sddd(ax,bx,cx) scanf("%d %d %d",&ax,&bx,&cx)
#define sfd(ax) scanf("%lf",&ax)
#define sfdd(ax,bx) scanf("%lf %lf",&ax,&bx)
#define pr(a) printf("%d\n",a)
#define plr(a) printf("%lld\n",a)    
int a[N],b[N],cap[N],vis[N],cnt[N],match[N][N],n,L;
vector<int> G[N];
bool Find(int x)
{
    for(int i=0;i<G[x].size();++i)
    {
        int y = G[x][i];
        if(!vis[y])
        {
            vis[y] = 1;
            if(cnt[y] < cap[y]) 
            {
                match[y][++cnt[y]] = x;
                return true;
            }
            else
            {
                for(int i=1;i<=cap[y];++i)
                {
                    int tt = match[y][i];
                    if(Find(tt))
                    {
                        match[y][i] = x;
                        return true;
                    }
                }
            }
        }
    }
    return false;
}
int slove()
{
    int ans = 0;
    for(int i=1;i<=n;++i)
    {
        met0(vis);
        if(Find(i)) ans++;
    }
    return ans;
}
int main()
{
    sdd(n,L);
    for(int i=1;i<=n;++i) sdd(a[i],b[i]);
    for(int i=1;i<=L;++i)
    {
        int x;sdd(x,cap[i]);
        for(int j=1;j<=n;++j)
        {
            if(x >= a[j] && x <= b[j])
            {
                G[j].pb(i);
            }
        }
    }
    int ans = slove();
    pr(ans);
    //system("pause");
    return 0;
}

2.网络流。
建立一个超级源点和汇点.
可以建立联系的牛和护肤品之间建立一条容量为1的边.
然后源点和护肤品之间建立一条容量限制为coveri的边。
汇点和各牛建立容量为1的边.over..
代码？（咕咕咕.）