题解：P4209 学习小组

· · 题解

前言

一个成功者，看似无战不胜，但他终究是给自己留下了退路的；

一个难题，看似无法战胜，但它终究是无数琐碎的知识拼合成的。

OI 何尝不是这样呢？

Solution

限制这么多，还得算最小代价，一看就是费用流了。

一个一个来处理限制。

限制一

“每个学生只愿意参加其中的一些学习小组，且一个学生最多参加 k 个学习小组”：对于这条限制，很明显学生不一定只选 1 个，也不一定 k 个全选。我们可以从每个表示学生的点向超汇连一条容量为 k-1，费用为 0 的边，同时从超源向每个代表学生的点连一条容量为 k，费用为 0 的边。这表示若学生选其他的学习小组会带来大于 0 的支出，那么就让这个学生干脆不选，直接流到汇点，同时也保证了直接流到汇点的流量小于 k，即每个学生都至少选了一个小组。

这条容量为 k-1 的边，就相当于一条留个自己选择的退路。

限制二

“每个学生参加学习小组财务处都收一定的手续费”：这个很好处理，因为题要求求最小的支出，所以直接从每个学生向其愿意的学习小组 i 连一条容量为 1，费用为 -F_i 的边（这样不会出现负环，不信你自己试试）。

限制三

“若有 a 个学生参加第 i 个学习小组，财务处支付奖励 C_i\times a^2 元”：先想没有平方时（支出 C_i \times a 时）咋做：从学习小组出发，向汇点连一条容量为 inf，费用为 C_i 的边。

但加上平方后，费用的表示看上去十分有十一分的不好做，有什么办法把平方的表示变一变吗？有的兄弟，有的，这是一个你小学就学过的规律：

1+3+5+\cdots+(2k-1)=k^2

那么对于这个问题，我们将从学习小组到支出为 C_i \times a^2 的边拆解成多个费用为连续奇数乘 C_i 的边相加，并将这些边的容量均设为 1，因为我们跑的是最小费用最大流，所以当有流到达这些边时，会优先走最小的能走的边，得到的费用之和自然也为 a^2 了。

平方看似无法战胜，但又何尝不是几个微不足道的奇数拼合而成的呢？

Code & 总结

费用流问题，要巧用容量刻画限制，同时也要深刻理解最大流的前提下才有最小费用的底层逻辑。

至于代码实现，按上述方法建图，跑一遍最小费用最大流即可，此处 Dinic 代码奉上：

#include<bits/stdc++.h>
#define YUANSHEN ios_base::sync_with_stdio(0);
#define QIDONG cin.tie(0);cout.tie(0);
#define int long long 
#define endl '\n'
#define inf 1e9
using namespace std;
const int maxn=1e5+10;

int n,m,k,head[maxn],dis[maxn],cur[maxn],tot=1,s,t,f[maxn];

struct node{int to,nex,w,c;}edge[maxn];

void add(int u,int v,int w,int c){
    edge[++tot]={v,head[u],w,c};
    head[u]=tot;
    edge[++tot]={u,head[v],0,-c};
    head[v]=tot;
}

bool vis[maxn];

bool spfa(){
    for(int i=1;i<=t;i++)dis[i]=inf,cur[i]=head[i];
    queue<int> q;
    q.push(s);
    dis[s]=0;
    while(q.size()){
        int u=q.front(); q.pop(); vis[u]=false;
        for(int i=head[u];i;i=edge[i].nex){
            int v=edge[i].to;
            if(dis[v]>dis[u]+edge[i].c && edge[i].w){
                dis[v]=dis[u]+edge[i].c;
                if(!vis[v])vis[v]=true,q.push(v);
            }
        }
    }
    return dis[t]!=inf;
}

int dfs(int u,int minn){
    if(u==t)return minn;
    int detel=minn;
    vis[u]=true;
    for(int &i=cur[u];i;i=edge[i].nex){ //当前弧优化
        int v=edge[i].to;
        if(vis[v] || dis[v]!=dis[u]+edge[i].c || !edge[i].w)continue;
        int d=dfs(v,min(detel,edge[i].w));
        detel-=d;
        edge[i].w-=d; edge[i^1].w+=d;
        if(!detel)break;
    }
    vis[u]=false;
    return minn-detel;
}

void solve(){ //Dinic求解费用流
    int cost=0;
    while(spfa())cost+=dis[t]*dfs(s,inf);
    cout<<cost;
}

signed main(){
    YUANSHEN QIDONG
    cin>>n>>m>>k;
    s=n+m+1,t=s+1;
    for(int i=1;i<=m;i++){
        int c; cin>>c;
        for(int k=1;k<=2*n-1;k+=2)add(i+n,t,1,c*k); //学习小组向汇点连边
    }
    for(int i=1;i<=m;i++)cin>>f[i];
    for(int i=1;i<=n;i++){
        string str; cin>>str; int sum=0;
        for(int j=0;j<m;j++)if(str[j]-'0'==1)add(i,n+j+1,1,-f[j+1]),sum++; //收费
        add(s,i,min(k,sum),0); add(i,t,min(sum-1,k-1),0); //细节：k与sum要取一个min
    }
    solve();
    return 0;
}