Burn the Linked Camp zoj 2770（差分约束）

本文主要是介绍Burn the Linked Camp zoj 2770（差分约束），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接： ZOJ - 2770

题意：1-n排列的军营， 每个军营的容量为ci， m个猜测（i, j, k）i-j军营一共k人；问最少有多少人；

x[i]-x[i-1]>=num;-->x[i-1]-x[i]>=-num, x[i]-x[i-1]>=0;x[0]-x[i]>=0;

得图：i-1-->i=-num, i-->i-1=0, 0-->i=0;

(i, j, k)-->x[j]-x[i-1]<=k;

得：i-1-->j=k;

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string.h>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
int n, m;
struct node{int v, next;long long w;
}edge[310000];
int head[1100], cnt, num[1100];
void add(int u, int v, long long w){edge[cnt].v=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++;
}
long long c[1100], sum[1100], dis[1100];
bool vis[1100];
queue<int> q;
bool SPFA(){for(int i=1; i<=n; i++){dis[i]=-INF;num[i]=0;vis[i]=false;} dis[0]=0;vis[0]=true;num[0]=1;q.push(0);while(!q.empty()){int temp=q.front();q.pop();vis[temp]=false;for(int i=head[temp]; i!=-1; i=edge[i].next){int to=edge[i].v;if(dis[to]<dis[temp]+edge[i].w){dis[to]=dis[temp]+edge[i].w;if(!vis[to]){vis[to]=true;q.push(to);num[to]++;if(num[to]>n) return false;}}}}return true;
}
int main(){while(~scanf("%d%d", &n, &m)){memset(head, -1, sizeof(head));for(int i=1; i<=n; i++){scanf("%lld", &c[i]);add(i-1, i, 0);add(i, i-1, -c[i]);add(0, i, 0);}int a, b;long long z;for(int i=1; i<=m; i++){scanf("%d%d%lld", &a, &b, &z);add(a-1, b, z);}if(!SPFA()) printf("Bad Estimations\n");else printf("%lld\n", dis[n]);}return 0;
}

这篇关于Burn the Linked Camp zoj 2770（差分约束）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---