题解：P4209 学习小组

· · 题解

被题目吓哭了...

题意

给定 n 个学生和 m 个学习小组，一个学生最多加入 k 个学习小组，加入小组还要给手续费，每个学生只能加入自己愿意加的小组。如果有 a 个学生加入学生小组 i，会奖励 C_i \times a^2 元。要求求出在参与学生尽量多（不是每个小组的总人数）的情况下，求出最少支出。（即总手续费减总奖励金额）。

建图

先别看那个恶心人的 C_i \times a^2。我们先建其他的边。

我们建一个超级源点 s，从 s 连向学生 i 的边，容量为 k，费用为 0。这代表规定一个学生最多加入 k 个学习小组。

接着对于第 i 个学生加入第 j 个学习小组，我们连从 i 向 j 的边，容量为 1，费用为负的 f_j，代表交 f_j 的手续费。

最后，就是连学生 i 到汇点的边。

Q：为什么是要连学生到汇点？

A：因为学生有可能选小组，也可能不选。

那有人就说了，学生 i 到汇点的边容量是 k，费用是 0 对吧。

当然不对！

回归题目，题目在要求求出最小支出前，还要求参与学生尽量多。

这该怎么解决？

当然是强迫参加咯！

什么意思？即我们将学生 i 到汇点的边的容量设为 k-1，费用为 0。这代表着我们强迫学生至少参加一个小组。

解决完以上问题，我们就该考虑那个恶心人的 C_i\times a^2。

我们很容易想到一个式子：

x^2=1+3+5+······+（2x-1）

我们受到启发，从小组 j 连到汇点的 n 条边，容量为 1，费用为 C_j \times(2t-1)，t 表示连汇点的第 t 条边。

建图毕。

代码

按上述方法建图，再跑一遍最小费用最大流即可。 :::success[Code]

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn=1e5+10;
const int inf=1e8;
int n,m,k,s,t;
int f[maxn];
char ch[110][110];
struct node{
    int to,next,cap,cost;
}e[2*maxn];
int head[maxn],tot=1;
void add(int u,int v,int cap,int cost){
    e[++tot].to=v;
    e[tot].cap=cap; e[tot].cost=cost;
    e[tot].next=head[u];
    head[u]=tot;
}
int dis[maxn],cur[maxn];
bool st[maxn],vis[maxn];
bool spfa(){
    queue<int> q;
    fill(st+1,st+2*n+m+2,0);
    fill(dis+1,dis+2*n+m+2,inf);
    q.push(s); dis[s]=0; st[s]=1;
    while(!q.empty()){
        int u=q.front(); q.pop();
        st[u]=0;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].cost&&e[i].cap){
                dis[v]=dis[u]+e[i].cost;
                if(!st[v]){
                    q.push(v);
                    st[v]=1;
                }
            }
        }
    }
    return dis[t]!=inf;
}
int dfs(int u,int flow,int &mincost){
    if(u==t) return flow;
    int used=flow;
    vis[u]=1;
    for(int i=cur[u];i;i=e[i].next){
        cur[u]=i;
        int v=e[i].to;
        if(dis[v]==dis[u]+e[i].cost&&e[i].cap&&!vis[v]){
            int rlow=dfs(v,min(used,e[i].cap),mincost);
            e[i].cap-=rlow; e[i^1].cap+=rlow;
            used-=rlow; mincost+=rlow*e[i].cost;
            if(used==0) break;
        }
    }
    vis[u]=0;
    return flow-used;
}
int dinic(int &mincost){
    int ans=0;
    while(spfa()){
        memcpy(cur,head,sizeof(head));
        ans+=dfs(s,inf,mincost);
    }
    return ans;
}
int edge[maxn];
int dfs1(){
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(!e[edge[i]].cap) cnt++;
    }
    return cnt;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>k; s=0,t=n+m+1;
    for(int i=1;i<=n;i++) add(s,i,k,0),add(i,s,0,0);
    for(int i=1;i<=m;i++){
        int c;
        cin>>c;
        for(int j=1;j<=n;j++){
            int w=c*(2*j-1);
            add(n+i,t,1,w); add(t,n+i,0,-w);
        }
    }
    for(int i=1;i<=m;i++) cin>>f[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char ch;
            cin>>ch;
            if(ch=='0') continue;
            add(i,n+j,1,-f[j]); add(n+j,i,0,f[j]);
        }
    }
    for(int i=1;i<=n;i++) add(i,t,k-1,0),add(t,i,0,0);
    int mincost=0; dinic(mincost);
    cout<<mincost;
    return 0;
}

:::