POJ1201(差分约束)

Sn表示集合Z中小于等于i的元素个数

5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

1.Z集合中范围在[ai,bi]的整数个数 S[bi] - S[ai - 1] 至少为 Ci，得不等式

S2 - S7 <= -3

S7 - S10 <= -3

S5 - S8 <= -1

S0 - S3 <=-1

S9 - S11 <= -1

2. S[i-1]到S[i]之间最多有1个数，最少有0个数

S[i] - S[i-1] <= 1

S[i-1] - S[i] <= 0

minm为所有区间左端点最小值， maxm为所有区间右端点最大值，最终要求 S[maxm] - S[minm] 的最小值 S[minm-1] - S[maxm] <= -M

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <queue>
 7 using namespace std;
 8 #define N 50005
 9 #define M 150005
10 #define inf 9999999
11 int dis[N],head[N],vis[N],in[N];
12 int n,size,maxm,minm;
13 struct Edge
14 {
15     int v,w,next;
16     Edge(){}
17     Edge(int V,int W,int NEXT):v(V),w(W),next(NEXT){}
18 }edge[M];
19 
20 void Init()
21 {
22     size = 0;
23     memset(head,-1,sizeof(head));
24 }
25 
26 void InsertEdge(int u,int v,int w)
27 {
28     edge[size] = Edge(v,w,head[u]);
29     head[u] = size++;
30 }
31 
32 bool spfa()
33 {
34     for(int i=minm-1; i<=maxm; i++)
35     {
36         dis[i] = inf;
37         vis[i] = 0;
38         in[i] = 0;
39     }
40     queue<int> Q;
41     while(!Q.empty()) Q.pop();
42     dis[maxm] = 0;
43     in[maxm] = vis[maxm] = 1;
44     Q.push(maxm);
45     while(!Q.empty())
46     {
47         int u = Q.front();
48         Q.pop();
49         vis[u] = 0;
50         for(int i=head[u]; i!=-1; i=edge[i].next)
51         {
52             int v = edge[i].v;
53             if(dis[v] > dis[u] + edge[i].w)
54             {
55                 dis[v] = dis[u] + edge[i].w ;
56                 if(!vis[v])
57                 {
58                     vis[v] = 1;
59                     in[v]++ ;
60                     if(in[v]>n) return 0;
61                     Q.push(v);
62                 }
63             }
64         }
65     }
66     return 1;
67 }
68 
69 int main()
70 {
71     while(scanf("%d",&n)!=EOF)
72     {
73         Init();
74         int u,v,w;
75         maxm = 0 ; minm = 50050;
76         for(int i=0; i<n; i++)
77         {
78             scanf("%d%d%d",&u,&v,&w);
79             maxm = max(maxm,v);
80             minm = min(minm,u);
81             InsertEdge(v,u-1,-w);
82         }
83         for(int i=minm; i<=maxm; i++)
84         {
85             InsertEdge(i-1,i,1);
86             InsertEdge(i,i-1,0);
87         }
88         if(spfa())
89         printf("%d
",-dis[minm-1]);
90     }
91     return 0;
92 }

View Code