POJ1201 Intervals（差分约束系统）

与ZOJ2770一个建模方式，前缀和当作点。

对于每个区间[a,b]有这么个条件，S_a-S_b-1>=c，然后我就那样连边WA了好几次。

后来偷看数据才想到这题还有两个隐藏的约束条件。

这题前缀和表示的是区间内点存在的个数，因此：

S_i>=S_i-1
S_i-S_i-1<=1

所以，差分约束系统的构图一定要考虑全面。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #include<algorithm>
 5 using namespace std;
 6 #define MAXN 65555
 7 #define MAXM 411111
 8 #define INF (1<<30)
 9 
10 struct Edge{
11     int v,cost,next;
12 }edge[MAXM];
13 int head[MAXN],NE,NV,vs;
14 void addEdge(int u,int v,int cost){
15     edge[NE].v=v; edge[NE].cost=cost; edge[NE].next=head[u];
16     head[u]=NE++;
17 }
18 
19 int d[MAXN];
20 bool vis[MAXN];
21 void SPFA(){
22     for(int i=0; i<NV; ++i){
23         vis[i]=0; d[i]=INF;
24     }
25     vis[vs]=1; d[vs]=0;
26     queue<int> que;
27     que.push(vs);
28     while(!que.empty()){
29         int u=que.front(); que.pop();
30         for(int i=head[u]; i!=-1; i=edge[i].next){
31             int v=edge[i].v;
32             if(d[v]>d[u]+edge[i].cost){
33                 d[v]=d[u]+edge[i].cost;
34                 if(!vis[v]){
35                     vis[v]=1;
36                     que.push(v);
37                 }
38             }
39         }
40         vis[u]=0;
41     }
42 }
43 int main(){
44     int n,a,b,c;
45     while(~scanf("%d",&n)){
46         memset(head,-1,sizeof(head));
47         NE=0; 
48         int maxu=0;
49         while(n--){
50             scanf("%d%d%d",&a,&b,&c);
51             ++a; ++b;
52             addEdge(b,a-1,-c);
53             maxu=max(b,maxu);
54         }
55         vs=maxu+1; NV=vs+1;
56         for(int i=1; i<=maxu; ++i) addEdge(i-1,i,1);
57         for(int i=1; i<=maxu; ++i) addEdge(i,i-1,0);
58         for(int i=0; i<=maxu; ++i) addEdge(vs,i,0);
59         SPFA();
60         int res=INF;
61         for(int i=0; i<=maxu; ++i) res=min(res,d[i]);
62         printf("%d
",-res);
63     }
64     return 0;
65 }