刷题集--稳定的奶牛分配

题意：农夫约翰有N(1<=N<=1000)只奶牛，每只奶牛住在B(1<=B<=20)个奶牛棚中的一个。当然，奶牛棚的容量有限。有些奶牛对它现在住的奶牛棚很满意，有些就不太满意了。
农夫约翰想要重新安排这些奶牛，使得奶牛的满意度尽可能相同，尽管有可能这意味者所有的奶牛都不喜欢新分配的奶牛棚。
每只奶牛都按顺序给出她喜欢的奶牛棚。在某个分配方案中，一只奶牛的满意度等于她对她的奶牛棚的评价等级。你的工作是找出一种分配方案使得没有奶牛棚超出它的容量，而且奶牛给分配到的奶牛棚的评价等级的相对范围（即分配到的等级最高的奶牛棚和等级最低的奶牛棚之间的差值）尽可能的小。

暴枚答案以及最小位置跑最大流判断是否可行即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1110,M=80010;
const int s=0,t=1100;
int n,m,tot=-1;
int hd[N],cur[N],nxt[M],las[M],to[M],dep[N],ans;
int mp[1010][30],rl[30];
void add(int u,int v,int w)
{
    nxt[++tot]=hd[u],to[tot]=v,las[tot]=w,hd[u]=tot;
    nxt[++tot]=hd[v],to[tot]=u,las[tot]=0,hd[v]=tot;
}
bool bfs()
{
    queue<int>q;int nw;
    memset(dep,0,sizeof dep);
    q.push(s),dep[s]=1;
    while(!q.empty())
    {
        nw=q.front(),q.pop();
        for(int i=hd[nw];i!=-1;i=nxt[i])
        {
            if(!dep[to[i]]&&las[i])
            {
                dep[to[i]]=dep[nw]+1;
                q.push(to[i]);
            }
        }
    }
    return dep[t];
}
int dfs(int pos,int flow)
{
    if(pos==t)return ans+=flow,flow;
    int tp;
    for(int &i=cur[pos];i!=-1;i=nxt[i])
    {
        if(las[i]&&dep[to[i]]==dep[pos]+1)
        {
            tp=dfs(to[i],min(flow,las[i]));
            if(tp)
            {
                las[i]-=tp,las[i^1]+=tp;
                return tp;
            }
        }
    }
    return 0;
}
int dinic()
{
    ans=0;
    while(bfs())
    {
        for(int i=0;i<=t;i++)cur[i]=hd[i];
        while(dfs(s,2e9));
    }
    return ans;
}
void build(int x,int y)
{
    tot=-1;
    memset(hd,-1,sizeof hd);
    for(int i=1;i<=m;i++)add(s,i,rl[i]);
    for(int i=1;i<=n;i++)
    {
        for(int j=y;j<=x+y;j++)
            add(mp[i][j],i+m,1);
        add(i+m,t,1);  
    }      
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&mp[i][j]);
    for(int i=1;i<=m;i++)scanf("%d",&rl[i]);    
    for(int i=0;i<=m;i++)
    {
        for(int j=1;i+j<=m;j++)
        {
            build(i,j);
            if(dinic()==n)return printf("%dn",i+1),0;
        }
    }
}

最后

以上就是可靠小丸子为你收集整理的刷题集--稳定的奶牛分配的全部内容，希望文章能够帮你解决刷题集--稳定的奶牛分配所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。