[BZOJ1061]志愿者招募

2019-11-06 08:07:57

字体：大中小

来源：转载

供稿：网友

题目链接：BZOJ1061

题目大意 题目讲的清楚简洁，这里就不讲了(其实是因为我不知道该怎么复述

题解推荐：感谢BYVoid的超强题解

分析上面的题解讲得很清楚，这里具体讲一下怎么建图。 1. 将所有项移到左边之后，设正项为流入，负项为流出。 2. 观察发现，对于第i $i$ 种自愿者，其在第S[i] $S[i]$ 个等式出现正项，第T[i]+1 $T[i]+1$ 项出现负项；对于Y[i] $Y[i]$ ，其在第i $i$ 项出现负项，第i+1 $i+1$ 项出现正项。 3. 所以T[i]+1 $T[i]+1$ 向S[i] $S[i]$ 连边，容量为INF $INF$ ，费用为V[i] $V[i]$ ；i $i$ 向i+1 $i+1$ 连边，容量为INF $INF$ ，费用为0 $0$ 。 4. 对于常数项，若为正值，由S $S$ 向其连边，容量为绝对值；反之，其向T $T$ 连边，容量为绝对值。

上代码

#include <queue>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N = 1e3 + 10;const int M = 15e3 + 10;const int INF = 0x3f3f3f3f;int n, m, S, T;int head[N], len = 2;struct nodeLib { int to, nxt, flow, cost; inline void add(int a, int b, int c, int d) { to = b, flow = c, cost = d; nxt = head[a], head[a] = len++; }} lib[M << 1];inline int read() { int ans = 0; char ch = getchar(); while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0', ch = getchar(); return ans;}int ps[M];inline void makePath(int a, int b, int c, int d) { lib[len].add(a, b, c, d); lib[len].add(b, a, 0, -d);}void init() { n = read(), m = read(); S = 0, T = n + 2; for (int i = 1; i <= n; i++) ps[i] = read(); for (int i = n + 1; i >= 1; i--) { ps[i] -= ps[i - 1]; if (ps[i] > 0) makePath(i, T, ps[i], 0); else if (ps[i] < 0) makePath(S, i, -ps[i], 0); } for (int i = 1; i <= m; i++) { int a = read(), b = read(), c = read(); makePath(b + 1, a, INF, c); } for (int i = 1; i <= n; i++) makePath(i, i + 1, INF, 0);}queue <int> Q;bool inQ[N];int dist[N], PReE[N], preV[N];bool SPFA() { memset(dist, 0x3f, sizeof(dist)); dist[S] = 0, inQ[S] = true, Q.push(S); while (!Q.empty()) { int tmp = Q.front(); Q.pop(), inQ[tmp] = false; for (int p = head[tmp]; p; p = lib[p].nxt) { int now = lib[p].to; if (lib[p].flow && dist[now] > dist[tmp] + lib[p].cost) { dist[now] = dist[tmp] + lib[p].cost; preV[now] = tmp, preE[now] = p; if (!inQ[now]) inQ[now] = true, Q.push(now); } } } return dist[T] != INF;}int MCMF() { int ans = 0; while (SPFA()) { int maxf = INF; for (int p = T; p != S; p = preV[p]) maxf = min(maxf, lib[preE[p]].flow); for (int p = T; p != S; p = preV[p]) lib[preE[p]].flow -= maxf, lib[preE[p] ^ 1].flow += maxf; ans += dist[T] * maxf; } return ans;}int main() { init(); printf("%d/n", MCMF()); return 0;}

以上

上一篇：laravel queue:work & queue:listen

下一篇：c语言实现顺序表