你以为我拉了嘿嘿其实我真的拉了

cqbzlym · 2023-07-18 15:54:14 · 题解

题解 P4209。

以来就给我整不会了。怎么处理平方？怎么控制参与总学生最多？其中一定又有什么我不知道的奇技淫巧。

一切尽在连边。

• 处理学生与社团间的选择关系

  把学生向社团连边。学生只能选取某社团一次，故容量为 1。

  一个学生选取某个社团并不会立即对最终花费带来可计算的影响，因为最终花费由该社团参与的 所有学生平方数 决定。

  故这一步我们先不慌计算社团的代价，只算参与社团本身需要的手续费 F_i。但是需要注意到手续费是财务部的收入而非支出，故实际边权为 -F_i，计算答案时视作负支出（明显不会因此而产生负环，因此可以放心加边）。

• 处理学生的选择数量上限

  学生最多只能选择 K 个社团，为保证这一点，我们将源点向学生连边，容量为 K。

  很明显，代价也不在此处计算，故令费用为 0。

• 保证代价最小

  一开始，我认为最小费用最大流一定会找到最小费用，这个处理是无意义的，后来被打脸了。

  我们若欲在此图中寻得最小费用最大流，则 流一定最大。

  而学生的流入容量为 K，为了满流，学生一定会尽可能多地选择社团，那么费用就会噌噌上涨。回到目标，即保证学生都选取至少一个社团时，支出最小。

  那我们只要给机会让学生可以只选取一个社团就好了（当然也可以是两个、三个……）。

  故让学生向终点连边，容量为 K-1，那么学生可以在选取了所有比较赚的社团后就不再选了，选这条边达到满流。同样因为该边流量只有 K-1，学生为了满流就只能再选至少一个社团，满足题意。

  不选社团明显是没有手续费和社团支出的，故费用为 0。

• 处理社团本身支出

  问题在于如何处理 a 这个平方项。

  对于平方，我们可以联想到许多数学知识，譬如完全平方、平方差等，这里用到了平方差。

  假如原来的代价是 C_i\times x^2，又加入了一个人，那么费用会变成 C_i\times (x + 1)^2。由平方差得两者之差为 C_i\times (2\times x + 1)。当 x - 1 取为任意正整数时，2\times x + 1 即为所有奇数。

  所以我们将社团向汇点连边，连很多条边，每条边表示 新增一个团员的代价，容量为 1 表示一个新增团员，费用为从 1 开始，一直到 2\times (N - 1) + 1 的所有奇数。

那么问题到这里就算处理完了。直接上费用流即可。

不知道我的代码遭遇了哪家宇宙射线的侵蚀，Dinic 死活过不去，换成 EK 就过了。同学们如果发现自己的 Dinic 过不了也可以试试换 EK。

#define int long long
namespace XSC062 {
using namespace fastIO;
const int maxn = 405;
const int inf = 1e18;
const int maxm = 5e5 + 5;
struct _ {
    int v, c, w, n;
    _() {}
    _(int v1, int c1, int w1, int n1) {
        v = v1, c = c1, w = w1, n = n1;
    }
};
_ u[maxm];
bool inq[maxn];
int n, m, k, x, res;
int gs, gt, tot = 1;
int c[maxn], f[maxn];
int h[maxn], dis[maxn];
int fl[maxn], pre[maxn];
inline int min(int x, int y) {
    return x < y ? x : y;
}
inline bool SPFA(int s, int n) {
    std::queue<int> q;
    std::fill(dis + 1, dis + n + 1, inf);
    q.push(s), dis[s] = 0, inq[s] = 1;
    pre[s] = inf, pre[gt] = 0, fl[s] = inf;
    while (!q.empty()) {
        int f = q.front();
        q.pop(), inq[f] = 0;
        for (int i = h[f]; i; i = u[i].n) {
            if (u[i].c == 0)
                continue;
            int v = u[i].v, w = u[i].w;
            if (dis[v] > dis[f] + w) {
                pre[v] = i ^ 1;
                dis[v] = dis[f] + w;
                fl[v] = min(fl[f], u[i].c);
                if (!inq[v])
                    inq[v] = 1, q.push(v);
            }
        }
    }
    return pre[gt];
}
inline void SSP(int s, int n) {
    int p, mn, d;
    while (SPFA(s, n)) {
        mn = fl[gt], d = 0;
        for (p = gt; p != s; p = u[pre[p]].v) {
            u[pre[p]].c += mn;
            u[pre[p] ^ 1].c -= mn;
            d += u[pre[p] ^ 1].w;
        }
        res += mn * d;
    }
    return;
}
inline void add(int x, int y, int c, int w) {
    u[++tot] = _(y, c, w, h[x]);
    h[x] = tot;
    return;
}
inline void readx(int &x) {
    char ch = nec();
    while (ch != '0' && ch != '1')
        ch = nec();
    x = ch - '0';
    return;
}
int main() {
    read(n), read(m), read(k);
    gs = n + m + 1, gt = gs + 1;
    for (int i = 1; i <= m; ++i) {
        read(c[i]);
        for (int j = 0; j < n; ++j) {
            add(i + n, gt, 1,
                    (2 * j + 1) * c[i]);
            add(gt, i + n, 0,
                    -(2 * j + 1) * c[i]);
        }
    }
    for (int i = 1; i <= m; ++i)
        read(f[i]);
    for (int i = 1; i <= n; ++i) {
        add(gs, i, k, 0);
        add(i, gs, 0, 0);
        add(i, gt, k - 1, 0);
        add(gt, i, 0, 0);
        for (int j = 1; j <= m; ++j) {
            readx(x);
            if (x == 1) {
                add(i, j + n, 1, -f[j]); // 负代价
                add(j + n, i, 0, f[j]);
            }
        }
    }
    SSP(gs, gt);
    print(res, '\n');
    return 0;
}
} // namespace XSC062
#undef int