本人的代码如下,已经验证 MCMF 模板没有问题,建图部分似乎也没有问题,可以通过样例与 #1 #3 数据点。
节点的定义如下:[1,N] 为早上节点,[1+N,N+N] 为晚上节点,源点 2N+1,汇点 2N+2
#include <bits/extc++.h>
#define inline __always_inline
#define init_buf(l, r, buf, val) for (auto m_it = l; m_it <= r; m_it++) buf[m_it] = val
template <typename key_t, typename cmp_fn>
using priority_queue = __gnu_pbds::priority_queue<key_t, cmp_fn>;
using pii = std::pair<int, int>;
const size_t INF = 0x7fffffff;
const size_t N_LIMIT = 500001, M_LIMIT = 5000005;
void read(int &x)
{
char ch = getchar();
while (!isdigit(ch)) ch = getchar();
for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
}
namespace MCMF
{
int n, s, t;
struct edge_t
{
int w, c;
int v, tail;
};
edge_t edge[M_LIMIT];
int top = 2;
int head[N_LIMIT], active[N_LIMIT];
inline void add_edge(int u, int v, int w, int c)
{
edge[top] = {w, c, v, head[u]};
head[u] = top++;
edge[top] = {0, -c, u, head[v]};
head[v] = top++;
}
priority_queue<pii, std::greater<pii>> pq;
decltype(pq)::point_iterator its[N_LIMIT];
char visit[N_LIMIT];
int dis[N_LIMIT], h[N_LIMIT];
bool Dijkstra()
{
memset(visit, 0, sizeof(visit));
init_buf(1, n, dis, INF); dis[s] = 0;
init_buf(1, n, its, pq.push({dis[m_it], m_it}));
while (!pq.empty())
{
auto u = pq.top().second;
pq.pop();
visit[u] = 1;
for (auto e = head[u]; e; e = edge[e].tail)
{
auto v = edge[e].v, w = edge[e].w, c = edge[e].c + h[u] - h[v];
if (w != 0 && dis[v] - dis[u] > c)
{
dis[v] = dis[u] + c;
pq.modify(its[v], {dis[v], v});
}
}
}
return dis[t] != INF;
}
int64_t total_cost = 0;
int64_t total_flow = 0;
int dfs(int u = s, int flow = INF)
{
if (u == t)
return flow;
visit[u] = 1;
int subflow, sum = 0;
for (int e = active[u]; e; e = edge[e].tail)
{
active[u] = e;
int v = edge[e].v, w = edge[e].w, c = edge[e].c + h[u] - h[v];
if (visit[v] || w == 0 || dis[u] + c != dis[v])
continue;
subflow = dfs(v, std::min(flow - sum, w));
if (subflow != 0)
{
edge[e].w -= subflow;
edge[e ^ 1].w += subflow;
sum += subflow;
if (sum == flow)
return flow;
}
}
return sum;
}
inline void Dinic()
{
while (Dijkstra())
{
memcpy(active, head, sizeof(head));
memset(visit, 0, sizeof(visit));
int64_t subflow = dfs();
total_flow += subflow;
total_cost += (int64_t)(dis[t] + h[t]) * subflow;
init_buf(1, n, h, h[m_it] + dis[m_it]);
}
}
} // namespace MCMF
int N;
int r[2001];
int p, m, f, n, s;
int main()
{
freopen64("P1251_4.in", "r", stdin);
read(N);
for (int i = 1; i <= N; i++)
read(r[i]);
read(p), read(m), read(f), read(n), read(s);
MCMF::n = (N << 1) + 2;
MCMF::s = N << 1 | 1;
MCMF::t = (N << 1) + 2;
for (int i = 1; i <= N; i++)
MCMF::add_edge(MCMF::s, i, INF, p);
for (int i = 1; i <= N; i++)
MCMF::add_edge(MCMF::s, i + N, r[i], 0);
for (int i = 1; i <= N; i++)
MCMF::add_edge(i, MCMF::t, r[i], 0);
for (int i = 1; i + 1 <= N; i++)
MCMF::add_edge(i + N, i + N + 1, INF, 0);
for (int i = 1; i + m <= N; i++)
MCMF::add_edge(i + N, i + m, r[i], f);
for (int i = 1; i + n <= N; i++)
MCMF::add_edge(i + N, i + n, r[i], s);
MCMF::Dinic();
printf("%ld", MCMF::total_cost);
return 0;
}