lp3980 NOI2008 志愿者招募

一开始YY了一种连边方式，就是源点向第一个点连边，第一个点向最后一个点连边，每个边的流量是1，希望能通过一些奇奇怪怪的约束条件来保证能从1跑到n。
但是很快这个想法就被枪毙了——每一天需要消耗的人力是不同的。
怎么办呢？
我们可以考虑一种（我瞎取名叫）替换法的建模方法。
具体来说就是，先确定一个最大流，然后将其中的一些流量替换为必须要通过实际需要的路径才能跑过，这样就保证了答案的合法性。

#include<iostream>
#include<cstdio>
#include<queue>

const int INF = 0x3f3f3f3f;
inline int Min(int A,int B){
	return A<B?A:B;
}
inline int Max(int A,int B){
	return A>B?A:B;
}

struct ee{
	int v;
	int w;
	int c;
	int nxt;
}e[400005];
int h[20005],et=-1;
inline void Eadd(int U,int V,int W,int C){
	e[++et]=(ee){V,W,C,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W,int C){
	Eadd(U,V,W,C);
	Eadd(V,U,0,-C);
}
int n,m,s,t,vis[20005],dis[20005],val[20005],nw[20005],fa[20005];
std::queue<int> q;
inline bool SPFA(){
	for(int i=1;i<=t;++i){
		vis[i]=0,dis[i]=INF,val[i]=INF;
	}
	dis[s]=0,vis[s]=1,fa[t]=-1;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		vis[p]=0;
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(e[i].w>0&&dis[e[i].v]>dis[p]+e[i].c){
				dis[e[i].v]=dis[p]+e[i].c;
				fa[e[i].v]=p;
				nw[e[i].v]=i;
				val[e[i].v]=Min(e[i].w,val[p]);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q.push(e[i].v);
				}
			}
		}
	}
	return fa[t]!=-1;
}

long long ans=0,ans2=0;
inline void EK(){
	int p;
	while(SPFA()){
		p=t;
		ans2+=val[t];
		ans+=val[t]*dis[t];
		while(p!=s){
			e[nw[p]].w-=val[t];
			e[nw[p]^1].w+=val[t];
			p=fa[p];
		}
	}
}
int a[20005],tot=0;
//tot不能想当然地取最大值，而应该取和。
//这是因为，过程中可能存在一些情况，使得先雇佣某个志愿者会更优。 
void init(){
	scanf("%d%d",&n,&m);
	s=n+2,t=n+3;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		tot+=a[i];
	}
	++tot;
	add(s,1,tot,0),add(n+1,t,tot,0);
	for(int i=1;i<=n;++i){
		add(i,i+1,tot-a[i],0);
	}
	int l,r,c;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&l,&r,&c);
		add(l,r+1,tot,c);
	}
	EK();
	printf("%lld\n",ans);
}

int main(){
	init();
	return 0;
}