POJ1201Intervals(差分约束系统)

题目说[ai, bi]区间内和点集Z至少有ci个共同元素，那也就是说如果我用Si表示区间[0,i]区间内至少有多少个元素的话，

那么Sbi - Sai >= ci,这样我们就构造出来了一系列边，权值为ci，但是这远远不够，因为有很多点依然没有相连接起来

（也就是从起点可能根本就还没有到终点的路线）,此时，我们再看看Si的定义，也不难写出0<=Si - Si-1<=1的限制条

件，虽然看上去是没有什么意义的条件，但是如果你也把它构造出一系列的边的话，这样从起点到终点的最短路也就

顺理成章的出现了。

还是严格按照差分的意思来解题。

 1 #include<cstring>
 2 #include<cmath>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cstdio>
 6 #include<queue>
 7 #define N 50007
 8 #define INF 2000000009
 9 using namespace std;
10 
11 int n,S,T;
12 int dis[N],ins[N];
13 int cnt,head[N],Next[N*4],rea[N*4],val[N*4];
14 
15 void add(int u,int v,int fee)
16 {
17     Next[++cnt]=head[u];
18     head[u]=cnt;
19     rea[cnt]=v;
20     val[cnt]=fee;
21 }
22 void Spfa()
23 {
24     for (int i=0;i<=S;i++)
25         dis[i]=-INF,ins[i]=0;
26     queue<int>q;
27     q.push(S);ins[S]=1;dis[S]=0;
28     while(!q.empty())
29     {
30         int u=q.front();q.pop();
31         for (int i=head[u];i!=-1;i=Next[i])
32         {
33             int v=rea[i],fee=val[i];
34             if (dis[v]<dis[u]+fee)
35             {
36                 dis[v]=dis[u]+fee;
37                 if (!ins[v])
38                 {
39                     ins[v]=1;
40                     q.push(v);
41                 }
42             }
43         }
44         ins[u]=0;
45     }    
46 }
47 int main()
48 {
49     while(~scanf("%d",&n))
50     {
51         cnt=0;
52         memset(head,-1,sizeof(head));
53         S=50001;
54         for (int i=1,x,y,z;i<=n;i++)
55         {
56             scanf("%d%d%d",&x,&y,&z);
57             if (x-1==-1) x=S+1;
58             add(x-1,y,z);
59         }
60         add(S,0,0);T=50000;
61         for (int i=1;i<=50000;i++)
62             add(i-1,i,0);
63         add(0,S,-1);
64         for (int i=1;i<=50000;i++)
65             add(i,i-1,-1);
66         Spfa();
67         printf("%d
",dis[T]);        
68     }
69 }