差分约束系统——你能忍受得糖果数量

　　poj3159

题目大意：分糖，a 能忍受分的糖果数 最多比b少c个，给你一系列这些关系，求x能忍受y最多多几个

学习了差分约束系统，了解了不等式<=以及>=对应得最短路最长路得转化，数形结合，也就很简单了，不过这个题有bug啊，正常得spfa中队列过不去，看了题解才知道都没过去哈哈哈，然后学习了模拟栈得用法（注释中），还是很好的~~

#include <iostream>
#include <queue>
#include <cstdio>
#include <string.h>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 3e4 + 3e2;
const int maxm = 1e5 + 6e4;
struct node{
    int to,cost;
    int pre;
}edge[maxm];
int id[maxn],cnt;
int vis[maxn];
int dis[maxn];
int S[maxn];//模拟栈
void init(int n)
{
    memset(edge,0,sizeof(edge));
    memset(id,-1,sizeof(id));
    for(int i = 1;i <= n;i++)
    {
        vis[i] = 0;dis[i] = inf;
    }
    cnt = 0;
}
void add(int from,int to,int cost)
{
    edge[cnt].to = to;
    edge[cnt].cost = cost;
    edge[cnt].pre = id[from];
    id[from] = cnt++;
}
void spfa(int s,int n)
{
    vis[s] = 1,dis[s] = 0;
    int top = 0;//表示站内元素个数，并且充当索引功能

    S[top] = 1;
    top++;
    while(top)
    {
        int now = S[--top];
        vis[now] = 0;
        for(int i = id[now];~i;i = edge[i].pre)
        {
            int to = edge[i].to;
            int cost = edge[i].cost;
            if(dis[to] > dis[now] + cost)
            {
                dis[to] = dis[now] + cost;
                if(!vis[to])
                {
                    vis[to] = 1;
                    S[top++] = to;
                }
            }
        }
    }
}
int main()
{
    int n,m,a,b,x;
    while(~scanf("%d%d",&n,&m))
    {
        init(n);
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&x);
            add(a,b,x);
        }
        spfa(1,n);
        printf("%d
",dis[n]);
    }
    return 0;
}

 感慨一下:原理非常可怕的spfa以及链式前向星，现在觉得和并查集基础dfsbfs差不多了，感觉信手什么来了~~，熟能生巧，多练多炼多恋吧~~