自动搬运

查看原文

来自洛谷，原作者为

	cqbzlym 自见者不明，自是者不彰

搬运于2025-08-24 21:57:41，当前版本为作者最后更新于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