BZOJ3442:学习小组 费用流

思路:

一开始YY了一个上下界最小费用流,结果有负圈...看来只有消圈姿势对才能搞了.

其实只有一个问题就是如何用最大流来限制参加的人数尽可能多,我们可以连接:

\[S->i~Maxcap=k~Cost=0\]

\[i->T~Maxcap=k-1~Cost=0\]

这样就确保了最大流中每个人必定会走\(1\)的流量.

剩下的就水了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<algorithm>
#include<queue>
using namespace std;
 
#define INF 0x3f3f3f3f
 
int cnt;
struct CostFlowSolver{
    int head[210],next[2000010],end[2000010],flow[2000010],cost[2000010],ind;
    int d[210],ld[210],lb[210];bool inq[210];queue<int>q;
    inline void reset(){ind=0,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f,int c){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f,cost[q]=c;}
    inline void make(int a,int b,int f,int c){addedge(a,b,f,c),addedge(b,a,0,-c);}
    inline bool spfa(int S,int T){
        memset(d,0x3f,sizeof d),d[S]=0,inq[S]=1,q.push(S);
        while(!q.empty()){
            int i=q.front();q.pop(),inq[i]=0;for(int j=head[i];j!=-1;j=next[j])if(flow[j]&&d[end[j]]>d[i]+cost[j]){
                d[end[j]]=d[i]+cost[j],ld[end[j]]=i,lb[end[j]]=j;if(!inq[end[j]])inq[end[j]]=1,q.push(end[j]);
            }
        }return d[T]!=INF;
    }
    inline int Mincost(int S,int T){
        int res=0,Min,i;
        while(spfa(S,T)){for(Min=INF,i=T;i^S;i=ld[i])Min=min(Min,flow[lb[i]]);for(i=T;i^S;i=ld[i])flow[lb[i]]-=Min,flow[lb[i]^1]+=Min;res+=Min*d[T];}
        return res;
    }
}SteinsGate;
 
int c[110],f[110];
int main(){
    int n,m,k;scanf("%d%d%d",&n,&m,&k);register int i,j;
    for(i=1;i<=m;++i)scanf("%d",&c[i]);for(i=1;i<=m;++i)scanf("%d",&f[i]);
 
    cnt=n+m;int S=0,T=++cnt;
    SteinsGate.reset();
    for(i=1;i<=n;++i)SteinsGate.make(S,i,k,0);
    for(i=1;i<=n;++i)if(k>1)SteinsGate.make(i,T,k-1,0);
    int x;for(i=1;i<=n;++i)for(j=1;j<=m;++j){scanf("%1d",&x);if(x)SteinsGate.make(i,n+j,1,-f[j]);}
    for(j=1;j<=m;++j)for(i=1;i<=n;++i)SteinsGate.make(n+j,T,1,c[j]*(2*i-1));
 
    printf("%d",SteinsGate.Mincost(S,T));
    return 0;
}