poj1716-差分约束+spfa

这题目和上题目1201一样，就只改一下权重。
注意一点，这题目边比较多，哎，我开搭配100*10005，过了。后来想改为循环队列，没想到原来while（head < tail）没有改为while（head != tail）记过wa了好几次。
其他没什么了。。。
总之记住一个原则，求最小值，>=,求最长路。求最大值，<=，求最短路。这也是这两道题目学到的经。。。。这个要搞不清楚，那也只是看了别人代码能懂，但是自己写不出来。至于证明可以参考acm论文。
代码：
[cpp]
#include <stdio.h>

#define maxN 10005//最大边条数
#define inf 0x7fffffff//最大距离

struct Edge
{
    int v, w, next;
}edge[4 * maxN];//边集

int dis[maxN];
bool vis[maxN]; www.zzzyk.com
int queue[maxN];
int preEdge[maxN];//同一个顶点的前一条边

int edgeNum,n,maxn;

void addEdge(int u, int v, int w)//添加一条边
{
    edge[edgeNum].v = v;
    edge[edgeNum].w = w;
    edge[edgeNum].next = preEdge[u];
    preEdge[u] = edgeNum ++;
}

void spfa()//spaf算法
{
    int head = 0, tail = 1;
    for (int i = 0; i <= maxn; ++ i)
    {
        dis[i] = -inf;
    }
    queue[head] = 0;
    dis[0] = 0;
    while (head != tail)
    {
        int u = queue[head];
        vis[u] = true;
        for (int p = preEdge[u]; p != 0; p = edge[p].next)
        {
            int v = edge[p].v;
            if (dis[v] < dis[u] + edge[p].w)
            {
                dis[v] = dis[u] + edge[p].w;
                if (!vis[v])
                {
                    vis[v] = true;
                    queue[tail] = v;
                    tail ++;
                    if (tail == maxN)
                    {
                        tail = 0;
                    }
                }
            }
        }
        vis[u] = false;
        head ++;
        if (head == maxN)
        {
            head = 0;
        }
    }
}

int main()
{
    scanf("%d", &n);
    edgeNum = 1;
    maxn = 0;
    while (n --)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        if (v + 1 > maxn)
        {
            maxn = v + 1;
        } www.zzzyk.com
        addEdge(u, v + 1, 2);
    }
    for (int i = 0; i <= maxn; ++ i)
    {
        addEdge(i, i + 1, 0);
        addEdge(i + 1, i, -1);
    }
    spfa();
    printf("%d\n", dis[maxn]);
    return 0;
}
作者：zhang20072844

补充：软件开发 , C++ ,