題意是：fy作為班長，分發糖果給每個孩子，而分發的過程要滿足一個約束條件就是 B - ?A <= C 表示B所得到的糖果不能比A多c個。問fy（n點代表）所能得到的糖果數量與sp（0點代表）所能得到的糖果數目的最大差值。 很明顯的差分約束題目根據B - A <= C建立約束圖，求最短路得到最大值。不過這里ka queue的實現。用stack來實現才能ac。。。

#include <cstdio> #include <cstring> #include <iostream> #define maxn 30007 #define maxm 150004 using namespace std;struct node {int v,w;int next; }g[maxm]; int pre[maxn],cnt,dis[maxn]; int stack[maxm*10]; bool ins[maxn]; int n,m; const int inf = 99999999;void init() {int i;for (i = 0; i < maxn; ++i){pre[i] = -1;ins[i] = false;}cnt = 0; } void add(int u,int v,int w) {g[cnt].v = v;g[cnt].w = w;g[cnt].next = pre[u];pre[u] = cnt++; } bool spfa(int u) {int i;int top = 0;for (i = 0; i <= n; ++i) dis[i] = inf;dis[u] = 0;ins[u] = true; stack[++top] = u;while (top){int cur = stack[top--];ins[cur] = false;for (i = pre[cur]; i != -1; i = g[i].next){int v = g[i].v,w = g[i].w;if (dis[v] > dis[cur] + w){dis[v] = dis[cur] + w;if (!ins[v]){stack[++top] = v;ins[v] = true;}}}}return true; } int main() {int i,a,b,c;init();scanf("%d%d",&n,&m);for (i = 0; i < m; ++i){scanf("%d%d%d",&a,&b,&c);add(a,b,c);}spfa(1);printf("%d\n",dis[n]);return 0; }

　　

轉載于:https://www.cnblogs.com/E-star/archive/2012/06/23/2559371.html

總結

以上是生活随笔為你收集整理的pku 3159 Candies 差分约束的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。