差分约束的入门题。比2770稍复杂，需要稍微转化一下。

    设S[i]是前i个数中选出的个数，则ai到bi的个数即S[bi] - S[ai-1]。因此有S[bi] - S[ai-1] >= ci。另外有S[i] - s[i - 1] >= 0 && S[i] - S[i - 1] <= 1，故建图。

    使图中每一组uv，满足

1. S[ai - 1] <= S[bi] + ci
2. S[i] <= S[i - 1] + 1
3. S[i - 1] <= S[i]

    当不满足时，更新即可。

    tips：因为此题必有解（题给出），因此bellmanford只需更新至全部满足即可。

#include <cstdio>
#include <string>

#define inf 99999

struct Edge
{
 int u, v, w;
} edge[50001];

int n, a[50001], mn, mx;

void init()
{
 int i;
 for(i = 0; i < 50001; i ++)
  a[i] = 0;
 mx = 1, a[0] = 0, mn = inf;
}

bool bellman_ford()
{
 int i, t, f = 1;
 // pa();
 // must satisfy following aspects:
 // s[v] <= s[u] - w
 // s[i] <= s[i - 1] + 1
 // s[i - 1] <= s[i]
 while(f)
 {
  f = 0;
  for(i = 0; i < n; i ++)
  {
   t = a[edge[i].u] + edge[i].w;
   if(a[edge[i].v] > t)
   {
    a[edge[i].v] = t;
    f = 1;
   }
  }
  for(i = mn; i <= mx; i ++)
  {
   t = a[i - 1] + 1;
   if(a[i] > t)
   {
    a[i] = t;
    f = 1;
   }
  }
  for(i = mx; i >= mn; i --)
  {
   t = a[i];
   if(a[i - 1] > t)
   {
    a[i - 1] = t;
    f = 1;
   }
  }
 }
 return true;
}

int main()
{
 //freopen("in.txt", "r", stdin);
 while(scanf("%d", &n) != EOF)
 {
  init();
  int i, u, v, w;
  for(i = 0; i < n; i ++)
  {
   scanf("%d %d %d", &u, &v, &w);
   edge[i].u = v, edge[i].v = u - 1, edge[i].w = -w;
   if(mn > u) mn = u;
   if(mx < v) mx = v;
  }
  
  bellman_ford();
  //pa();
  printf("%d\n", a[mx] - a[mn - 1]);
 }
 return 0;
}

评论