BZOJ3442 学习小组 <费用流>

Problem

学习小组

Time Limit: $5 Sec$
Memory Limit: $128 MB$

Description

坑校准备鼓励学生参加学习小组。
共有$n$个学生，$m$个学习小组，每个学生有一定的喜好，只愿意参加其中的一些学习小组，但是校领导为学生考虑，规定一个学生最多参加$k$个学习小组。财务处的大叔就没那么好了，他想尽量多收钱，因为每个学生参加学习小组都要交一定的手续费，不同的学习小组有不同的手续费。然而，事与愿违，校领导又决定对学习小组组织者进行奖励，若有$a$个学生参加第i个学习小组，那么给这个学习小组组织者奖励$C_i\times a^2$元。在参与学生（而不是每个学习小组的人数总和）尽量多的情况下，求财务处最少要支出多少钱（若为负数，则输出负数）（$支出=总奖励费-总手续费$）。

Input

输入有若干行，第一行有三个用空格隔开的正整数$n、m、k$。接下来的一行有$m$个正整数，表示每个$C_i$。第三行有$m$个正整数，表示参加每个学习小组需要交的手续费$F_i$。再接下来有一个$n$行$m$列的矩阵，表若第$i$行$j$列的数字是$1$，则表示第$i$个学生愿意参加第$j$个学习小组，若为$0$，则为不愿意。

Output

输出只有一个整数，为最小的支出。

Sample Input

3 3 1
1 2 3
3 2 1
111
111
111

Sample Output

-2

Hint

样例解释
参与学生最多为$3$，每个学生参加一个学习小组，若有两个学生参加第一个学习小组，一个学生参加第二个学习小组（一定要有人参加第二个学习小组），支出为$-2$，可以证明没有更优的方案了。
数据范围与约定
$100\%$的数据，$0＜n\le 100，0＜m\le 90，0＜k\le m，0＜Ci\le 10，0＜Fi\le 100$。

标签：费用流

Solution

常规费用流建模。
建图：
每个学生为一个点，每个小组为一个点，共$n+m$个点。
对每个学生$p_i$，
$S\to p_i$ 流量$k$ 费用$0$ （限制最多选$k$个组）
$p_i\to T$ 流量$k-1$ 费用$0$ （限制至少选一个组）
对每个组$g_i$，
$g_i\to T$ 流量$1$ 费用$C_i\times (2j-1)$ 其中$j\in [1, n]$
即当前若有$x$个人，再多一个人会带来$C_i\times (x+1)^2-C_i\times x^2=C_i\times (2x+1)=C_i\times [2(x+1)-1]$的收益
学生和组之间则连边 $p_i\to g_j$ 流量$1$ 费用$-F_i$
跑小费流即可。

Code

#include <bits/stdc++.h>
#define MAX_N 500
#define MAX_M 50000
#define INF 0x7f7f7f7f
using namespace std;
int n, m, k, s, t, cnt, pr[MAX_N+5], cr[MAX_N+5], mxf, mic;
struct node {int v, c, w, nxt;} E[MAX_M+5];    int f[MAX_N+5];
void init() {s = 0, t = n+m+1, memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c, int w) {E[cnt] = (node){v, c, w, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c, int w) {insert(u, v, c, w), insert(v, u, 0, -w);}
bool SPFA() {
    queue <int> que;	bool inq[MAX_N+5];	int d[MAX_N+5], cr[MAX_N+5];
    memset(inq, false, sizeof inq), memset(d, INF, sizeof d);
    d[s] = 0, que.push(s), inq[s] = true, memset(cr, -1, sizeof cr);
    while (!que.empty()) {
        int u = que.front();	que.pop(), inq[u] = false;
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c, w = E[i].w;
            if (c && d[u]+w < d[v]) {
                d[v] = d[u]+w, cr[v] = i;
                if (!inq[v]) que.push(v), inq[v] = true;
            }
        }
    }
    if (d[t] == INF) return false;	int flow = INF;
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) flow = min(flow, E[i].c);
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) E[i].c -= flow, E[i^1].c += flow;
    mxf += flow, mic += d[t];	return true;
}
int main() {
    scanf("%d%d%d", &n, &m, &k), init();
    for (int i = 1; i <= n; i++) addedge(s, i, k, 0);
    for (int i = 1; i <= n; i++) addedge(i, t, k-1, 0);
    for (int i = 1; i <= m; i++) {
        int c;	scanf("%d", &c);
        for (int j = 1; j <= n; j++)
            addedge(i+n, t, 1, c*(2*j-1));
    }
    for (int i = 1; i <= m; i++) scanf("%d", f+i);
    for (int i = 1; i <= n; i++) {
        char s[MAX_N];	scanf("%s", s+1);
        for (int j = 1; j <= m; j++) if (s[j] == '1')
            addedge(i, j+n, 1, -f[j]);
    }
    while (SPFA()) ;	return printf("%d", mic), 0;
}