种树-洛谷P1250（差分约束）

传送门

令前缀和为s[i]，则⼀一个要求等价于 s[r] - s[l - 1] >= x。

题中还有别的要求，包括 s[i] - s[i - 1] <= 1 和 s[i] - s[i- 1] >= 0。

建一个超级原点s，把所有结点连到s（令s = n + 1）

差分约束系统规定的只是元素的相对关系

按照题意，相对关系不变时最后的答案尽可能小

因此最终答案应该是：dis[ n ] - min_dis

#include<cstdio>

#include<cstring>

#include<queue>

#include<algorithm>

using namespace std;

inline int read()

{

    int sum = ,p = ;

    char ch = getchar();

    while(ch < '' || ch > '')

    {

        if(ch == '-')

            p = -;

        ch = getchar();

    }

    while(ch >= '' && ch <= '')

    {

        (sum *= ) += ch - '';

        ch = getchar();

    }

    return sum * p;

}

const int maxn = ,maxm = ;

int n,m,s,cnt;

int dis[maxn],head[maxn];

bool vis[maxn];

struct edge

{

    int nxt,to,wei;

} e[maxn * ];

void add(int x,int y,int z)

{

    e[++cnt].nxt = head[x];

    e[cnt].to = y;

    e[cnt].wei = z;

    head[x] = cnt;

}

void spfa(int x)

{

    queue<int> q;

    q.push(x);

    for(int i = ; i <= n + ; i ++)

        dis[i] = 1e9;

    dis[s] = ;

    vis[s] = true;

    while(!q.empty())

    {

        int o = q.front();

        q.pop();

        vis[o] = false;

        for(int i = head[o]; i; i = e[i].nxt)

        {

            int v = e[i].to;

            if(dis[v] > dis[o] + e[i].wei)

            {

                dis[v] = dis[o]  + e[i].wei;

                if(!vis[v])

                {

                    q.push(v);

                    vis[v] = true;

                }

            }

        }

    }

}

int main()

{

    n = read(),m = read();

    s = n + ;

    memset(head,-,sizeof(head));

    for(int i = ; i <= n; i++)

        add(s,i,);

    int a,b,c;

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

    {

        a = read(),b = read(),c = read();

        add(b,a - ,-c);

    }

    for(int i = ; i <= n; i++)

    {

        add(i - ,i,);

        add(i,i - ,);

    }

    spfa(s);

    int ans = 1e9;

    for(int i=; i<=n; i++)

         ans = min(ans, dis[i]);

    printf("%d",dis[n] - ans);

    return ;

}