学步园

差分约束巧妙地将不等式的关系转换成图论中求最短路径时所用的三角形不等式

即如果dis[i]+map[i][j]<=dis[j]

交换一下得：dis[i]-dis[j]<=-map[i][j]

建边j->i     权值为-map[i][j];

核心的方法就是上面的东西了

用spfa求最短路

#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
const int INF = 9999999;
struct NODE{
int v,w;
int next;
}list[150010];
int tot;
int head[50010];
int dis[50010];
int vis[50010];
queue<int> Q;
int n,m;
void init()
{
int i;tot=0;
for(i=0;i<=150000;i++)
        list[i].w=INF;
    memset(head,-1,sizeof(head));
}
void add(int s,int t,int w)
{
    list[tot].v=t;
    list[tot].w=w;
    list[tot].next=head[s];
    head[s]=tot++;
}
void spfa(int src)
{
int i,j,u;
while(!Q.empty())  Q.pop();
    memset(vis,0,sizeof(vis));
for(i=0;i<=50000;i++)
        dis[i]=INF;
    Q.push(src);
    vis[src]=1;
    dis[src]=0;
while(!Q.empty())
    {
        u=Q.front();
        Q.pop();
        vis[u]=0;
for(j=head[u];j!=-1;j=list[j].next)
        {
int e=list[j].v;
if(dis[e]>list[j].w+dis[u])
            {
                dis[e]=list[j].w+dis[u];
if(!vis[e])
                {
                    Q.push(e);
                    vis[e]=1;
                }
            }
        }
    }
}
int main()
{
int n,a,b,c,i,j;
int mx,mi;
while(scanf("%d",&n)!=EOF)
    {
        init();
        mx=0,mi=INF;
for(i=0;i<n;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            add(b,a-1,-c);
if(a<mi) mi=a;
if(b>mx) mx=b;
        }
for(i=mi;i<=mx;i++)
        {
            add(i-1,i,1);
            add(i,i-1,0);
        }
        spfa(mx);
        printf("%d\n",-dis[mi-1]);
    }
}

 

另一种不同的方法

#include<stdio.h>
#include<string.h>
int n,mx,my;
struct edge{
int u,v,w;
}e[50010];
int d[50010];
int solve()
{
int i,k;
bool flag=true;
while(flag)
     {
         flag=false;
for(i=0;i<n;i++)
         {
if(d[e[i].u]+e[i].w<d[e[i].v])
                 d[e[i].v]=d[e[i].u]+e[i].w,flag=true;
         }
for(i=my;i>=mx;i--)
if(d[i-1]>d[i])
                 d[i-1]=d[i],flag=true;
for(i=mx;i<=my;i++)
if(d[i]>d[i-1]+1)
                d[i]=d[i-1]+1,flag=true;
     }
return d[my]-d[mx-1];
}
int main()
{
int i,a,b,w,j;
while(scanf("%d",&n)!=EOF)
    {
        mx=50000,my=0;
        memset(d,0,sizeof(d));
for(i=0;i<n;i++)
        {
            scanf("%d%d%d",&a,&b,&w);
            e[i].u=b;
            e[i].v=a-1;
            e[i].w=-w;
if(mx>a) mx=a;
if(my<b) my=b;
        }
        printf("%d\n",solve());
    }
return 0;
}