BZOJ 3442 学习小组

题解：

神建图

普通的二分图费用流建完后

添加学生x->t 容量为k-1的边

表示尽量让x参加一个活动，剩下的k-1次机会可以不参加

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<queue>

using namespace std;

const int maxn=;

const int oo=;

int n,m,k;

int a[maxn],b[maxn];

int ans=;

struct Edge{

    int from,to,cap,flow,cost;

};

vector<int>G[maxn];

vector<Edge>edges;

void Addedge(int x,int y,int z,int w){

    Edge e;

    e.from=x;e.to=y;e.cap=z;e.flow=;e.cost=w;

    edges.push_back(e);

    e.from=y;e.to=x;e.cap=;e.flow=;e.cost=-w;

    edges.push_back(e);

    int c=edges.size();

    G[x].push_back(c-);

    G[y].push_back(c-);

}

int s,t,totn;

queue<int>q;

int inq[maxn];

int d[maxn];

int p[maxn];

int Spfa(int &nowflow,int &nowcost){

    for(int i=;i<=totn;++i){

        d[i]=oo;inq[i]=p[i]=;

    }

    d[s]=;q.push(s);

    while(!q.empty()){

        int x=q.front();q.pop();inq[x]=;

        for(int i=;i<G[x].size();++i){

            Edge e=edges[G[x][i]];

            if((e.cap>e.flow)&&(d[x]+e.cost<d[e.to])){

                d[e.to]=d[x]+e.cost;

                p[e.to]=G[x][i];

                if(!inq[e.to]){

                    q.push(e.to);

                    inq[e.to]=;

                }

            }

        }

    }

    if(d[t]==oo)return ;

    int x=t,f=oo;

    while(x!=s){

        Edge e=edges[p[x]];

        f=min(f,e.cap-e.flow);

        x=e.from;

    }

    nowflow+=f;nowcost+=f*d[t];

    x=t;

    while(x!=s){

        edges[p[x]].flow+=f;

        edges[p[x]^].flow-=f;

        x=edges[p[x]].from;

    }

    return ;

}

int Mincost(){

    int flow=,cost=;

    while(Spfa(flow,cost)){

    }

    return cost;

}

char ss[];

int main(){

    scanf("%d%d%d",&n,&m,&k);

    totn=n+m;s=++totn;t=++totn;

    for(int i=;i<=m;++i)scanf("%d",&a[i]);

    for(int i=;i<=m;++i)scanf("%d",&b[i]);

    for(int i=;i<=m;++i){

        for(int j=;j<=n;++j){

            Addedge(i+n,t,,(*j-)*a[i]-b[i]);

        }

    }

    for(int i=;i<=n;++i){

        scanf("%s",ss+);

        for(int j=;j<=m;++j){

            if(ss[j]=='')Addedge(i,j+n,,);

        }

    }

    for(int i=;i<=n;++i)Addedge(s,i,k,);

    for(int i=;i<=n;++i)Addedge(i,t,k-,);

    cout<<Mincost()<<endl;

    return ;

}