区间和一定要联系到前缀和。
- 这题，把前缀和看作点，从s到s
- 对于每一个营地i的容量cap，有这么个关系s-s<=cap；
- 对于每一个区间的评估i,j,k，有s-s>=k，即s-s<=k；
- 接下来就是连边了，对于v<=u+w由u向v连权w的边，超级源向n+1个点连权0的边。
- 最后跑SPFA，如果出现负环则无解；而有解的话，所求答案就在d[s]里，不过因为题目的前缀和是非负整数且要求的最少，所以就要让d中所有数都同时加上合适的数得到另一个真正所求的解。
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define INF (1<<30)
#define MAXN 1111
#define MAXM 22222 struct Edge{
int v,cost,next;
}edge[MAXM];
int head[MAXN],NE;
void addEdge(int u,int v,int cost){
edge[NE].v=v; edge[NE].cost=cost; edge[NE].next=head[u];
head[u]=NE++;
} int n,m,d[MAXN],cnt[MAXN];
bool vis[MAXN];
bool SPFA(){
for(int i=; i<=n; ++i){
vis[i]=; cnt[i]=; d[i]=INF;
}
vis[n+]=; cnt[n+]=; d[n+]=;
queue<int> que;
que.push(n+);
while(!que.empty()){
int u=que.front(); que.pop();
if(cnt[u]>n+) return ;
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(d[v]>d[u]+edge[i].cost){
d[v]=d[u]+edge[i].cost;
if(!vis[v]){
vis[v]=;
++cnt[v];
que.push(v);
}
}
}
vis[u]=;
}
return ;
}
int main(){
int a,b,c,cap[MAXN];
while(~scanf("%d%d",&n,&m)){
for(int i=; i<=n; ++i) scanf("%d",cap+i); memset(head,-,sizeof(head));
NE=;
for(int i=; i<=n; ++i) addEdge(i-,i,cap[i]);
for(int i=; i<=n; ++i) addEdge(n+,i,);
while(m--){
scanf("%d%d%d",&a,&b,&c);
addEdge(b,a-,-c);
}
if(SPFA()){
int tmp=INF;
for(int i=; i<=n; ++i) tmp=min(tmp,d[i]);
if(tmp<) d[n]-=tmp;
printf("%d\n",d[n]);
}else puts("Bad Estimations");
}
return ;
}