差分约束的入门题。比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，满足 S[ai - 1] <= S[bi] + ci S[i] <= S[i - 1] + 1 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;}        

评论