poj 1201/zoj 1508（差分约束）

以前用线段树做过这题。

dis[i]表示从0->i-1这i个数存在多少个数。

则有dis[b+1]-dis[a]>=c;

dis[i+1]-dis[i]>=0 && dis[i+1]-dis[i]<=1

转换成为：

dis[a]-dis[b+1]<=-c;

dis[i]-dis[i+1]<=0

dis[i+1]-dis[i]<=1

建图。dis[en]-dis[st]<=w.

View Code

 1 // File Name: 1508.cpp
 2 // Author: Missa
 3 // Created Time: 2013/2/20 星期三 0:41:05
 4 
 5 #include<iostream>
 6 #include<cstdio>
 7 #include<cstring>
 8 #include<algorithm>
 9 #include<cmath>
10 #include<queue>
11 #include<stack>
12 #include<string>
13 #include<vector>
14 #include<cstdlib>
15 #include<map>
16 #include<set>
17 using namespace std;
18 #define CL(x,v) memset(x,v,sizeof(x));
19 
20 const int maxn = 5e4+5;
21 const int maxm = 2e5+5;
22 const int inf = 0x3f3f3f3f;
23 struct edge
24 {
25     int v,c,next;
26 }p[maxm];
27 int n,m,dis[maxn],e,head[maxn];
28 int mmin,mmax;
29 void addedge(int u,int v,int c)
30 {
31     p[e].v=v;p[e].c=c;
32     p[e].next=head[u];head[u]=e++;
33 }
34 bool relax(int u,int v,int c)
35 {
36     if(dis[v]>dis[u]+c)
37     {
38         dis[v]=dis[u]+c;
39         return true;
40     }
41     return false;
42 }
43 void init()
44 {
45     CL(head,-1);
46     e=0;
47     mmin=inf;mmax=-1;
48     for(int i=0;i<m;i++)
49     {
50         int u,v,c;
51         scanf("%d%d%d",&u,&v,&c);
52         addedge(v+1,u,-c);
53         if(mmin>u) mmin=u;
54         if(mmax<v) mmax=v;
55     }
56     for(int i=mmin;i<mmax+1;i++)
57     {
58         addedge(i+1,i,0);
59         addedge(i,i+1,1);
60     }
61 }
62 int spfa(int src)
63 {
64     bool vis[maxn];CL(vis,0);
65     CL(dis,0x3f);
66     dis[src]=0;vis[src]=1;
67     queue<int>q;q.push(src);
68     while(!q.empty())
69     {
70         int pre=q.front();q.pop();
71         vis[pre]=0;
72         for(int i=head[pre];i+1;i=p[i].next)
73         {
74             if(relax(pre,p[i].v,p[i].c) && !vis[p[i].v])
75             {
76                 q.push(p[i].v);
77                 vis[p[i].v]=1;
78             }
79         }
80     }
81     return -(dis[mmin]-dis[mmax+1]);
82 }
83 int main()
84 {
85     while(~scanf("%d",&m))
86     {
87         init();
88         //cout<<mmin<<" "<<mmax<<endl;
89         printf("%d\n",spfa(mmax+1));
90     }
91     return 0;
92 }