又一次考试网络流爆零......
这一题一看就是网络流, 但是要怎么构图呢? 考虑到途中的一些因素, 首先, 每一种志愿者控制的区间范围为\(S_{i}\)到\(T_{i}\), 所以, 我们要使得每种志愿者只能控制这段区间, 其他的不能够控制, 其次, 每个时间都有一个最小的值, 也就是这条边(我们将时间段看为一条边更加方便)有一个下界, 想到了什么, 上下界网络流, 每条边都要符合上界和下界的约束, 没有学过的可以.
那么初始的构图也就出来了, 每个时间作为一条边, 那么由\(i\)向\(i + 1\)连一条边, 容量为\(INF - lower(i)\), 费用为0(由于人是控制一段区间的, 他在这段区间中的任意两个点流费用都为0, 可以看做这个人继续做事, 已经付钱了, 你得给我做完事才能走)(\(lower(i)\)代表时间\(i\)最少需要多少人, 其实这条边容量为\(INF\)没有问题, 假装上界为\(INF + lower(i)\)就可以了, 反正可以不停地流), 考虑到之前所说, 每个点只能约束自己的一段区间, 有点像循环流, 从\(S_{i}\)出发, 流到\(T_{i}\)就重新流, 但是这里由于\(T_{i}\)被看成了一条边, 所以我们需要在点\(T_{i} + 1\)往\(S_{i}\)连一条容量为\(INF\), 费用为\(c\)的边, 代表当前类\(i\)的志愿者控制且只能控制\(S_{i}\)到\(T_{i}\)这段时间.
最终构图是这样的: 每个点\(i\)向\(i + 1\)连边, 每个\(T_{i} + 1\)向\(S_{i}\)连边, 注意在每个点\(i\)向\(i + 1\)连边时, 由于你是默认这条边流了一个下界的, 你每个点的流量不一定平衡, 记录一下每个点流入和流出的差, 对于一条下界为\(x\)的边i -> i + 1, 记\(delta[i]\)为点\(i\)流入与流出的差, 则\(delta[i] -= x\), \(delta[i + 1] += x\), 连完所有边后, 注意到每个点的\(delta\)不一定为0, 对于\(delta\)大于或者小于0的情况, 戳上面那个吧, 有详细的介绍, 最后跑一遍无源汇上下界最小费用可行流就可以了, 也就是在构出的有源汇的图中跑一遍最小费用最大流即可.
具体代码
#include#include #include #include #define N 2005#define INF 1e9using namespace std;int n, m, S, T, delta[N], head[N], cnt = 1, p[N], vis[N]; struct node{ int from, to, next; long long flow, cost; } edge[100005];long long a[N], d[N]; inline int read(){ int x = 0, w = 1; char c = getchar(); while(c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * w;}inline void add(int u, int v, long long w, long long cost){ edge[++cnt] = { u, v, head[u], w, cost }; head[u] = cnt; edge[++cnt] = { v, u, head[v], 0, -cost }; head[v] = cnt; }bool SPFA(long long &cost){ memset(d, 0x3f, sizeof(d)); memset(a, 0x3f, sizeof(a)); queue q; q.push(S); d[S] = 0; vis[S] = 1; while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for(int i = head[u]; i; i = edge[i].next) { int v = edge[i].to; if(d[v] > d[u] + edge[i].cost && edge[i].flow > 0) { d[v] = d[u] + edge[i].cost; a[v] = min(a[u], edge[i].flow); p[v] = i; if(!vis[v]) { vis[v] = 1; q.push(v); } } } } if(d[T] == d[0]) return 0; cost += (a[T] * d[T]); for(int i = T; i != S; i = edge[p[i]].from) { edge[p[i]].flow -= a[T]; edge[p[i] ^ 1].flow += a[T]; } return 1; }int main(){ n = read(); m = read(); S = n + 2; T = S + 1; for(int i = 1; i <= n; i++) { int x = read(); add(i, i + 1, INF, 0); delta[i] -= x; delta[i + 1] += x; } for(int i = 1; i <= m; i++) { int u = read(), v = read(), c = read(); add(v + 1, u, INF, c); } for(int i = 1; i <= n + 1; i++) { if(delta[i] < 0) add(i, T, -delta[i], 0); if(delta[i] > 0) add(S, i, delta[i], 0); } long long cost = 0; while(SPFA(cost)); printf("%lld\n", cost); return 0;}