题意

编号为 1..N 的人, 每人有一个数;

需要满足

dj - di <= c

求1号的数与N号的数的最大差值.(略坑: 1 一定要比 N 大的...difference...不是"差别", 而是"做差"....)

思路

差分约束

差分约束顾名思义就是以"差值"作为约束条件的规划问题. 这个"差值"的特点使得这个问题可以转化为最短路问题(或最长路?)

由于SFPA(或Dijkstra)中的松弛操作:

d[v] <= d[i] + w;

移项之后可以得到

d[v] - d[u] <= w;

这和差分约束的方程形式相同. 并且也满足左边为未知量, 右边为常量; 于是可以建立有向图来解决这个问题.

将未知量设为顶点, 右边常量设为边权; 按照最短路问题的模型, 顶点的值即其到源的距离.则自然有"源"的值为0.

在差分约束系统中, 若有一组解X, 则X + k(任意实数)也为一组解.因为限制条件是"差值".

对应图的模型: 对于这样一组顶点, 源的选择会改变顶点的值, 但不会改变顶点的差值. <暂时没有更精确的理解>

本题中要求1号顶点和N号顶点的最大差值,感觉是"求最长路",为啥用一个求最短路的方法呢?

其实是在于两个问题的关系.

对于差分约束的方程组, 不等式可以全部都不取等号.

而最短路中不等式的用途则是不断调整各个变量的值, 使其对于每一个不等式(限制), 都取满足它的"上界", 即松弛操作. 对应实际操作就是选择一条路.

对于每一条和这个点相连的路, 都会被询问一遍, 如果有更短的路, 就选择新的路. 即是如果发现新的限制条件, 就要[至少]满足(取等号,"上界").

当所有的路都被询问, 亦即所有的限制条件都被满足之时, 得到的就是各个点的最短路长.

对于差分约束系统来说, 则是得到了使得每个约束条件中的两个值的差尽可能大的一组解. 当然对于1 和N来说, d[N] - d[1]是最大的.

取源为1时, d[N]即为答案.

如果要求在同一组约束之下1号和N号的最小差值, 则需要将不等式变形为

d[v] - d[u] >=  w;

连接 u -> v 的边, 边权为 w, 求最长路(只要将松弛操作改一下即可). 这样就得到了使得约束条件中的两个值的差尽可能小的一组解.

这是SPFA + stack. 看题解说queue会TLE, 就没有尝试了...

#include <cstdio>

#include <cstring>

#include <stack>

using namespace std;

const int MAXN = 30005;

const int MAXE = 150005;

const int INF = 0x3f3f3f3f;

struct pool

{

    int v,pre,w;

} p[MAXE];

int num,head[MAXN],d[MAXN],n,m;

bool inq[MAXN];

stack<int> s;

void clear()

{

    while(!s.empty())   s.pop();

    memset(head,0,sizeof(head));

    memset(d,0x3f,sizeof(d));

    memset(inq,false,sizeof(inq));

    num = 0;

}

int SPFA()

{

    d[1] = 0;

    inq[1] = true;

    s.push(1);

    while(!s.empty())

    {

        int u = s.top();

        s.pop();

        inq[u] = 0;

        for(int tmp=head[u],v;v=p[tmp].v,tmp;tmp=p[tmp].pre)

        {

            int w = p[tmp].w;

            if(d[v]>d[u]+w)

            {

                d[v] = d[u] + w;

                if(!inq[v])

                {

                    inq[v] = true;

                    s.push(v);

                }

            }

        }

    }

    return d[n];

}

void add(int u, int v ,int w)

{

    p[++num].v = v;

    p[num].w = w;

    p[num].pre = head[u];

    head[u] = num;

}

int main()

{

    while(scanf("%d %d",&n,&m)==2)

    {

        clear();

        while(m--)

        {

            int u,v,w;

            scanf("%d %d %d",&u,&v,&w);

            add(u, v, w);

        }

        printf("%d\n",SPFA());

    }

}

Dijkstra + priority_queue

那个排序,  用了long long + 位运算排的序orz..

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

const int MAXN = 30005;

const int MAXE = 150005;

typedef long long ll;

struct pool

{

    int v,pre,w;

}p[MAXE];

int num,head[MAXN],d[MAXN],m,n;

bool vis[MAXN];

priority_queue < ll, vector<ll>, greater<ll> > pq;

void clear()

{

    memset(head,0,sizeof(head));

    memset(d,0x3f,sizeof(d));

    memset(vis,false,sizeof(vis));

    num = 0;

    while(!pq.empty())  pq.pop();

}

void add(int u, int v, int w)

{

    p[++num].v = v;

    p[num].w = w;

    p[num].pre = head[u];

    head[u] = num;

}

int Dijkstra()

{

    d[1] = 0;

    pq.push((((ll)d[1])<<32)+1);

   // printf("push d[1] = 0\n");

    while(!pq.empty())

    {

        ll t = pq.top(); pq.pop();

        int k = t & ((1ll<<32)-1);

    //    printf("pop d[%d] = %d\n",k,d[k]);

        if(k==n)    return d[n];

        if(vis[k])  continue;

        vis[k] = true;

        for(int tmp=head[k],v,w;v=p[tmp].v,w=p[tmp].w,tmp;tmp=p[tmp].pre)

        {

            if(d[v]>d[k]+w)

            {

                d[v] = d[k] + w;

    //            printf("push d[%d] = %d\n",v,d[v]);

                pq.push((((ll)d[v])<<32)+v);

            }

        }

    }

    return d[n];

}

int main()

{

    while(scanf("%d %d",&n,&m)==2)

    {

        int u,v,w;

        clear();

        for(int i=0;i<m;i++)

        {

            scanf("%d %d %d",&u,&v,&w);

            add(u,v,w);

        }

        printf("%d\n",Dijkstra());

    }

}