【最小费用最大流】志愿者招募

网络流

传送门：CodeVS1803

NOI2008

思路：

  • 如果第i天需要x个人，就从i向i+1连容量为INF-x，费用为0的边，表示第i天
  • 如果有一个可工作x~y天费用为z的工人，就从x向y+1连一条容量INF，费用为z的边
  • 然后跑最小费用最大流
  • 因为最大流必定为INF，所以经过越过每天的流量必定为INF
  • 由于费用为0的边只有INF-x条，必有x条边是走有费用的边，表示租人

注意：最短路不要打错（MD我写完一个月以后才发现）

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
#define INF (LL)10000000000000
#define N 20030
#define M 200030
#define inc(x) (x=x%N+1)
#define min(x,y) ((x)<(y)?(x):(y))
LL n,m,s,t,sum,x,y,z,tot,head[N],dis[N],q[N],pre_v[N],pre_e[N],pre_f[N];
bool vis[N];
struct edge{LL v,cap,cost,rev,nxt;}e[(N+M)<<1];
void add(LL x,LL y,LL cap,LL cost){
	e[++tot].v=y; e[tot].cap=cap; e[tot].cost=cost;
	e[tot].rev=tot+1; e[tot].nxt=head[x]; head[x]=tot;
	e[++tot].v=x; e[tot].cap=0; e[tot].cost=-cost;
	e[tot].rev=tot-1; e[tot].nxt=head[y]; head[y]=tot;
}
LL cost_flow(LL s,LL t){
	LL cost=0;
	for (;;){
		for (int i=s;i<=t;i++){
			dis[i]=INF; vis[i]=0;
			pre_e[i]=0; pre_f[i]=0; pre_v[i]=0;
		}
		LL tt=0,ww=1; dis[s]=0; vis[s]=1; q[ww]=s; pre_f[0]=INF;
		while (tt!=ww){
			LL v=q[inc(tt)]; vis[v]=0;
			for (int i=head[v];i;i=e[i].nxt){
				if (e[i].cap>0 && dis[e[i].v]>dis[v]+e[i].cost){
					pre_e[e[i].v]=i; pre_f[e[i].v]=min(pre_f[v],e[i].cap); pre_v[e[i].v]=v;
					dis[e[i].v]=dis[v]+e[i].cost;
					if (!vis[e[i].v]){vis[e[i].v]=1; q[inc(ww)]=e[i].v;}
				}
			}
		}
		
		if (dis[t]>=INF) return cost;
		
		for (int i=t;i;i=pre_v[i]){
			e[pre_e[i]].cap-=pre_f[t];
			e[e[pre_e[i]].rev].cap+=pre_f[t];
			cost+=pre_f[t]*e[pre_e[i]].cost;
		}
	}
}
	
int main(){
	scanf("%lld%lld",&n,&m);
	s=0; t=n+1; add(s,1,INF,0);
	for (int i=1;i<=n;i++){scanf("%lld",&x); add(i,i+1,INF-x,0);}
	
	for (int i=1;i<=m;i++){
		scanf("%lld%lld%lld",&x,&y,&z);
		add(x,y+1,INF,z);
	}
	
	printf("%lld\n",cost_flow(s,t));
	
	return 0;
}