随笔-65  评论-6  文章-0  trackbacks-0
 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 #define MaxSize 50005
 5 #define inf 0x7ffffff
 6 struct  edge{
 7     int a,b,c;
 8 }eg[MaxSize];
 9 int n;
10 int d[MaxSize];
11 void bellman_Ford(int s,int e){
12     int i,j;
13     for(i=s;i<=e;i++)
14         d[i]=0;
15     //d[b]-d[a],由于b增加1过,因此,相当于d[a]为d[a-1],d[b]-d[a]的意义为[a,b]区间内符合条件的元素
16     for(i=s+1;i<e;i++){
17         bool flag=true;
18         for(j=0;j<n;j++)//约束条件,[a,b]区间内元素不少于c,即d[b]-d[a]>=c
19             if(d[eg[j].b]-eg[j].c<d[eg[j].a] )
20                 d[eg[j].a]=d[eg[j].b]-eg[j].c,flag=false;
21         for(j=e;j>s;j--)
22             if(d[j]<d[j-1])//约束条件,[m,m+1],d[m]<=d[m+1]
23                 d[j-1]=d[j],flag=false;
24         for(j=s+1;j<=e;j++)
25             if(d[j-1]+1<d[j])//d[m]+1>=d[m+1];
26                 d[j]=d[j-1]+1,flag=false;
27         if(flag)
28             return;
29     }
30 }
31 int main(){
32     freopen("in.txt","r",stdin);
33     while (~scanf("%d",&n)){
34         int i,s,e;
35         s=inf;
36         e=-inf;
37         for(i=0;i<n;i++){
38             scanf("%d %d %d",&eg[i].a,&eg[i].b,&eg[i].c);
39             eg[i].b++;//考虑到可能在计算会用到a-1,而当a=0时就越界了,因此整体加一
40             if(eg[i].a<s)
41                 s=eg[i].a;
42             if(eg[i].b>e)
43                 e=eg[i].b;
44         }
45         bellman_Ford(s,e);
46         printf("%d\n",d[e]-d[s]);
47     }
48     return 0;
49 }
posted on 2012-07-26 21:46 Leo.W 阅读(187) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理