Solution to CF756D Bacterial Melee。
给我整不会了。怎么处理平方？怎么控制参与总学生最多？其中一定又有什么我不知道的奇技淫巧。
一切尽在连边。
处理学生与社团间的选择关系
把学生向社团连边。学生只能选取某社团一次，故容量为 \(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