费用流
本题是一个是一个二分图带权匹配类问题,不难想到费用流求解,但与其他题目不同的是,在本题中,每道题目的费用跟这个人做完这道题的时间有关,于是运用常见技巧,以时间拆边,将每个人第$k$道做的题分开建$k$条边,流量为1,费用分别为$r、2r、3r……$,然后跑费用流即可,由于费用随时间递增,算法会自动按照时间顺序选择最优增广路。
动态加边费用流
显然上述连边边数将达到$nm$,无法通过此题,有一个显然的事情是,只有一个人做完了他的第一道题,他才会开始做第二道,于是我们根据每次增广路选择了哪个人,去加入那个人的下一条边,这样边数得到优化,在$luogu$可以压时限通过此题,$acwing$仍然超时。
贪心+最大流
我们的策略一定是每个人做的题尽可能挤在前面,考虑每个时间段的增广,应用现实生活经验(我不会证明),在靠前的时间段尽可能多做题,会使罚时变得更少,于是循环枚举时间段,每次对所有人动态增加$1$的流量去尝试增广,这次的罚时增量就是增广流量乘上当前时间,直到某次加完流量后仍无法增广则退出循环,跑的巨快。
动态加边费用流$54/60TLE$
#include <iostream>
#include <cstring>
using namespace std;
using i64 = long long;
const int N = 100010, M = 500010;
const int INF = 1e8;
int e[M], ne[M], h[N], f[M], w[M], idx;
int d[N], pre[N], incf[N];
int q[N];
bool vis[N];
int n, m, k, S, T;
int t, r, lim;
int g[510][510];
int cnt[510], ts[510], now[510];
void insert(int u, int v, int c, int d) {
e[idx] = v, ne[idx] = h[u], f[idx] = c, w[idx] = d, h[u] = idx++;
e[idx] = u, ne[idx] = h[v], f[idx] = 0, w[idx] = -d, h[v] = idx++;
}
bool spfa() {
int tt = 0, hh = 0;
memset(d, 0x3f, sizeof d);
memset(incf, 0, sizeof incf);
d[S] = 0, q[tt++] = S, incf[S] = 0x3f3f3f3f;
while (hh != tt) {
int t = q[hh++];
vis[t] = false;
if (hh == N) hh = 0;
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (d[j] > d[t] + w[i] && f[i]) {
d[j] = d[t] + w[i];
pre[j] = i;
incf[j] = min(incf[t], f[i]);
if (!vis[j]) {
q[tt++] = j;
if (tt == N) tt = 0;
vis[j] = true;
}
}
}
}
return incf[T] > 0;
}
void EK(int& flow, int& cost) {
flow = cost = 0;
while (spfa()) {
int t = incf[T];
flow += t, cost += t * d[T];
int cur;
for (int i = T; i != S; i = e[pre[i] ^ 1]) {
f[pre[i]] -= t, f[pre[i] ^ 1] += t;
if (i != S) cur = i;
}
++now[cur];
if (now[cur] <= lim && now[cur] <= cnt[cur])
insert(S, cur, 1, now[cur]);
}
}
int main() {
memset(h, -1, sizeof h);
cin >> n >> m >> r >> t >> k;
lim = t / r;
S = N - 1, T = S - 1;
for (int i = 1; i <= k; i++) {
int a, b;
cin >> a >> b;
cnt[a]++;
g[a][b] = 1;
}
for (int i = 1; i <= n; i++) {
now[i] = 1;
if (1 <= lim && 1 <= cnt[i]) insert(S, i, 1, 1);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
if (g[i][j])
insert(i, j + n, 1, 0);
}
for (int i = 1; i <= m; i++) insert(i + n, T, 1, 0);
int flow, cost;
EK(flow, cost);
cout << flow << ' ' << 1ll * cost * r << '\n';
for (int i = 0; i < idx; i += 2) {
int from = e[i ^ 1], to = e[i];
if (from <= n && to > n && f[i ^ 1]) {
cout << from << ' ' << to - n << ' ' << ts[from] << '\n';
ts[from] += r;
}
}
return 0;
}
最大流$1500ms$
#include <iostream>
#include <cstring>
using namespace std;
const int N = 10010, M = 2000010, INF = 0x3f3f3f3f;
int n, m, S, T;
int r, t, k, lim;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
int cnt[N];
int g[510][510];
int ts[510];
void insert(int u, int v, int d) {
e[idx] = v, ne[idx] = h[u], f[idx] = d, h[u] = idx++;
e[idx] = u, ne[idx] = h[v], f[idx] = 0, h[v] = idx++;
}
bool bfs() {
int hh = 0, tt = -1;
memset(d, -1, sizeof d);
q[++tt] = S, d[S] = 0, cur[S] = h[S];
while (hh <= tt) {
int t = q[hh++];
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (d[j] == -1 && f[i]) {
d[j] = d[t] + 1;
cur[j] = h[j];
if (j == T) return true;
q[++tt] = j;
}
}
}
return false;
}
int find(int u, int limit) {
if (u == T) return limit;
int flow = 0;
for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
cur[u] = i;
int j = e[i];
if (d[j] == d[u] + 1 && f[i]) {
int t = find(j, min(f[i], limit - flow));
if (!t) d[j] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
int dinic() {
int r = 0, flow;
while (bfs()) while (flow = find(S, INF)) r += flow;
return r;
}
int main() {
memset(h, -1, sizeof h);
cin >> n >> m >> r >> t >> k;
lim = t / r;
S = N - 1, T = S - 1;
for (int i = 1; i <= k; i++) {
int a, b;
cin >> a >> b;
cnt[a]++;
g[a][b] = 1;
}
for (int i = 1; i <= n; i++)
if (1 <= min(cnt[i], lim))
insert(S, i, 1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (g[i][j])
insert(i, j + n, 1);
for (int i = 1; i <= m; i++) insert(i + n, T, 1);
int res = dinic(), cost = res * r;
for (int i = 2; i <= lim; i++) {
for (int j = 1; j <= n; j++) f[2 * (j - 1)]++;
int delta = dinic();
if (!delta) break;
res += delta;
cost += 1ll * delta * i * r;
}
cout << res << ' ' << cost << '\n';
for (int i = 0; i < idx; i += 2) {
int from = e[i ^ 1], to = e[i];
if (from <= n && to <= n + m && f[i ^ 1]) {
cout << from << ' ' << to - n << ' ' << ts[from] << '\n';
ts[from] += r;
}
}
return 0;
}