poj1716 Integer Intervals（差分约束）

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <queue>
 7 using namespace std;
 8 typedef long long ll;
 9 typedef pair<int,int> PII;
10 #define MAXN 50010
11 #define REP(A,X) for(int A=0;A<X;A++)
12 #define INF  0x7fffffff
13 #define CLR(A,X) memset(A,X,sizeof(A))
14 struct node {
15     int v,d,next;
16 }edge[3*MAXN];
17 int head[MAXN];
18 int e=0;
19 void init()
20 {
21     REP(i,MAXN)head[i]=-1;
22 }
23 void add_edge(int u,int v,int d)
24 {
25     edge[e].v=v;
26     edge[e].d=d;
27     edge[e].next=head[u];
28     head[u]=e;
29     e++;
30 }
31 bool vis[MAXN];
32 int dis[MAXN];
33 void spfa(int s){
34     CLR(vis,0);
35     REP(i,MAXN)dis[i]=i==s?0:INF;
36     queue<int>q;
37     q.push(s);
38     vis[s]=1;
39     while(!q.empty())
40     {
41         int x=q.front();
42         q.pop();
43         int t=head[x];
44         while(t!=-1)
45         {
46             int y=edge[t].v;
47             int d=edge[t].d;
48             t=edge[t].next;
49             if(dis[y]>dis[x]+d)
50             {
51                 dis[y]=dis[x]+d;
52                 if(vis[y])continue;
53                 vis[y]=1;
54                 q.push(y);
55             }
56         }
57         vis[x]=0;
58     }
59 }
60 int main()
61 {
62     ios::sync_with_stdio(false);
63     int n;
64     int u,v,d;
65     int ans=0;
66     int maxn=0;
67     int minn=MAXN;
68     while(scanf("%d",&n)!= EOF&&n)
69     {
70         e=0;
71         init();
72         REP(i,n)
73         {
74             scanf("%d%d",&u,&v);
75             add_edge(u,v+1,-2);
76             maxn=max(maxn,v+1);
77             minn=min(u,minn);
78         }
79         for(int i=minn;i<maxn;i++){
80             add_edge(i+1,i,1);
81             add_edge(i,i+1,0);
82         }
83         spfa(minn);
84         cout<<-dis[maxn]<<endl;
85     }
86     return 0;
87 }