poj1201Intervals（差分约束）

设si[i+1]表示有不超过i的Z集合里面的数的个数，可以列出不等式si[b+1]-si[a]>=ci

另有隐含条件 si[i+1]-s[i]>=0 si[i]-s[i+1]>=-1 利用spfa求出最长路

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<stdlib.h>
 5 #include<queue>
 6 using namespace std;
 7 #define IN 50010
 8 #define INF 0x3f3f3f
 9 struct node
10 {
11     int u,v,w,next;
12 }men[IN*4];
13 int t,first[IN],n,dis[IN],vis[IN];
14 void init()
15 {
16     t = 0;
17     memset(first,-1,sizeof(first));
18 }
19 void add(int u,int v,int w)
20 {
21     men[t].u = u;
22     men[t].v = v;
23     men[t].w = w;
24     men[t].next = first[u];
25     first[u] = t;
26     t++;
27 }
28 void spfa(int st)
29 {
30     int i;
31     for(i = 0; i <= n ; i++)
32         dis[i] = -INF;
33     queue<int>q;
34     q.push(st);
35     memset(vis,0,sizeof(vis));
36     vis[st] = 1;
37     dis[st] = 0;
38     while(!q.empty())
39     {
40         int u = q.front();
41         vis[u] = 0;
42         q.pop();
43         for(i = first[u];i!=-1 ; i = men[i].next)
44         {
45             int v = men[i].v;
46             int w = men[i].w;
47             if(dis[v]<dis[u]+w)
48             {
49                 dis[v] = dis[u]+w;
50                 if(!vis[v])
51                 {
52                     vis[v] = 1;
53                     q.push(v);
54                 }
55             }
56         }
57     }
58 }
59 int main()
60 {
61     int i,a,b,c,ma=-1,mi = IN;
62     while(cin>>n)
63     {
64         init();
65         for(i = 1; i <= n ; i++)
66         {
67             cin>>a>>b>>c;
68             add(a,b+1,c);
69             if(b+1>ma)
70             ma = b+1;
71             if(a<mi)
72             mi = a;
73         }
74         for(i = mi ; i <= ma ; i++)
75         {
76             add(i,i+1,0);
77             add(i+1,i,-1);
78         }
79         spfa(mi);
80         cout<<dis[ma]<<endl;
81     }
82     return 0;
83 }