poj 1201 Intervals

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define maxn 500100
 5 using namespace std;
 6 
 7 int head[maxn],next[maxn],dis[maxn];
 8 bool vis[maxn];
 9 const int inf=1<<23;
10 int cnt[maxn],max1,min1;
11 int e,n,m,top;
12 int a[maxn];
13 
14 struct node
15 {
16     int u,v,c;
17     node(){}
18     node(int u,int v,int c):u(u),v(v),c(c){}
19 }p[maxn];
20 
21 void addnode(int u,int v,int c)
22 {
23     p[e]=node(u,v,c);
24     next[e]=head[u];head[u]=e++;
25 }
26 
27 bool relax(int u,int v,int c)
28 {
29     if(dis[v]<dis[u]+c)
30     {
31         dis[v]=dis[u]+c;
32         return true;
33     }
34     return false;
35 }
36 
37 void inti()
38 {
39     memset(head,-1,sizeof(head));
40     memset(next,-1,sizeof(next));
41     e=0;
42     top=-1,max1=-1;
43     min1=inf;
44     for(int i=0; i<n; i++)
45     {
46         int u,v,c;
47         scanf("%d%d%d",&u,&v,&c);
48         addnode(u,v+1,c);
49         min1=min(min1,u);
50         max1=max(max1,v+1);
51     }
52     for(int i=min1; i<max1; i++)
53     {
54         addnode(i,i+1,0);
55         addnode(i+1,i,-1);
56     }
57 }
58 
59 bool spfa()
60 {
61     memset(cnt,0,sizeof(cnt));
62     memset(vis,false,sizeof(vis));
63     for(int i=min1; i<=max1; i++) dis[i]=-inf;
64     a[++top]=min1;
65     vis[min1]=true;
66     dis[min1]=0;
67     while(top>-1)
68     {
69         int pre=a[top--];
70         vis[pre]=false;
71         for(int i=head[pre]; i+1; i=next[i])
72         {
73             if(relax(pre,p[i].v,p[i].c)&&!vis[p[i].v])
74             {
75                 if((++cnt[p[i].v])>n) return false;
76                 a[++top]=p[i].v;
77                 vis[p[i].v]=true;
78             }
79         }
80     }
81     return true;
82 }
83 
84 int main()
85 {
86     scanf("%d",&n);
87     inti();
88     spfa();
89     printf("%d
",dis[max1]-dis[min1]);
90     return 0;
91 }
View Code