230720 做题记录 // 费用流练习

XSC062 / 2023-07-20 / 原文

A. 订货

http://222.180.160.110:1024/contest/3820/problem/1

这个带继承关系的模型很熟悉，想到了猪那一题。所以我们试着仿照这个方式来建图。

题目提到了单位费用，这简直就是直接把边的费用拍你脸上嘲讽。

我们拉一个大源点，朝每个月连一条容量为无穷大、费用为当月购买单位费用的边，表示每个月的购买。

拉一个大汇点，每个月朝它连一条容量为当月需求量、费用为 \(0\) 的边，表示每个月的需求。

再让每个月朝下一个月连一条容量为仓库容量、费用为贮存费用的边，表示继承。跑一个最小费用最大流即可。

#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, S, x, res;
int gs, gt, tot = 1;
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 addf(int x, int y, int c, int w) {
	add(x, y, c, w), add(y, x, 0, -w);
	return;
}
int main() {
	read(n), read(m), read(S);
	gs = n + 1, gt = gs + 1;
	for (int i = 1; i <= n; ++i) {
		read(x);
		addf(i, gt, x, 0);
		if (i != n)
			addf(i, i + 1, S, m);
	}
	for (int i = 1; i <= n; ++i) {
		read(x);
		addf(gs, i, inf, x);
	}	
	SSP(gs, gt);
	print(res, '\n');
	return 0;
}
} // namespace XSC062
#undef int

B. 网络扩容

http://222.180.160.110:1024/contest/3820/problem/2

鉴于一道费用流不会无缘无故先让你求一遍最大流，我们先持观望态度，暂且认为最大流对题目有提示作用 ~~而不是说这道题就是个缝合怪~~

其实看完题我们就悟了，这怎么这么像上下界网络流那个差量网络呀，要不我们试试这么干？

我们先求得普通网络中的最大流，然后每条边减去流量，就成为了一个「差量网络 Pro」。那么我们现在就要通过扩容让该网络中的最大流变为 \(K\)。对于扩容的操作，不难想到把每条边的边权设为正无穷，然后费用设为扩容费用。

现在有了一个问题：原图中未留满的边，在现在的新网络中的残余容量应该如何处理呢？很简单，我们就把它当作已经扩过了这么多容，通过拆边操作拆出来一条容量为原图中残余容量、费用为 \(0\)「会员通道」，那么算法就会优先选择这条边。

怎么去控制流量为 \(K\)？联想到之前的拆边操作，我们考虑拆点。在 \(1\) 和 \(N\) 中任选一个拆开作为新的源点 / 汇点，新点和旧点之间的容量为 \(K\)、费用为 \(0\) 即可。

然后跑一个最小费用最大流就行。~~该说不说题目的正解思路引导做得还挺好的~~

其实注意到在跑完最大流之后，所有正向边的残余容量已经求得，只要在跑最大流时令所有边的费用为 \(0\)（毕竟最大流不关心费用），就可以沿用原图，只加新边再跑费用流。

#define int long long
namespace XSC062 {
using namespace fastIO;
const int inf = 1e18;
const int maxn = 1e3 + 5;
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;
	}
};
struct __ { int x, y, c, w; };
_ u[maxm];
__ w[maxm];
bool inq[maxn];
int n, m, k, res;
int gs, gt, tot = 1;
int h[maxn], dis[maxn];
int fl[maxn], pre[maxn];
int vis[maxn], now[maxn], dep[maxn];
inline int min(int x, int y) {
	return x < y ? x : y;
}
bool BFS(int n) {
	std::fill(vis + 1, vis + n + 1, 0);
	std::fill(dep + 1, dep + n + 1, 0); 
	std::queue<int> q;
	dep[gs] = 1, vis[gs] = 1;
	q.push(gs), now[gs] = h[gs];
	while (!q.empty()) {
		int f = q.front();
		q.pop();
		for (int i = h[f]; i; i = u[i].n) {
			int v = u[i].v, w = u[i].c;
			if (vis[v] == 1 || w == 0)
				continue;
			vis[v] = 1, now[v] = h[v];
			dep[v] = dep[f] + 1, q.push(v);
			if (v == gt)
				return 1;
		}
	}
	return 0;
}
int findP(int x, int flow = inf) {
	if (x == gt)
		return flow;
	int rest = flow, i;
	for (i = now[x]; rest && i; i = u[i].n) {
		int v = u[i].v, w = u[i].c;
		now[x] = i;
		if (dep[v] != dep[x] + 1 || w == 0)
			continue;
		int t = findP(v, min(rest, w));
		if (t == 0)
			dep[v] = 0;
		rest -= t;
		u[i].c -= t, u[i ^ 1].c += t;
	}
	return flow - rest;
}
inline int Dinic(int n) {
	int res = 0;
	while (BFS(n)) {
		int t = findP(gs);
		while (t) {
			res += t;
			t = findP(gs);
		}
	}
	return res;
}
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 addf(int x, int y, int c, int w = 0) {
	add(x, y, c, w), add(y, x, 0, -w);
	return;
}
int main() {
	read(n), read(m), read(k);
	gs = 1, gt = n;
	for (int i = 1; i <= m; ++i) {
		read(w[i].x), read(w[i].y);
		read(w[i].c), read(w[i].w);
		addf(w[i].x, w[i].y, w[i].c);
	}
	print(Dinic(n), ' ');
	gs = n + 1, addf(gs, 1, k, 0);
	for (int i = 1; i <= m; ++i)
		addf(w[i].x, w[i].y, inf, w[i].w);
	SSP(gs, gt);
	print(res, '\n');
	return 0;
}
} // namespace XSC062
#undef int