hdu 1384 差分约束系统+SPFA

要熟练应用差分约束还是很困难的。。。

题目的大意是：在每个区间[ai,bi]上至少选择ci个元素，构成一个集合S，使集合S中的元素最少；

不妨设f(a)为区间[0,a]上的选择的元素个数；

那么，由题意有f(b)-f(a-1)>=c,并且0<=(f(a)-f(a-1))<=1;

从而建图；

View Code

 1 #include<iostream>
 2 #include<queue>
 3 #include<cstring>
 4 const int N=50004;
 5 const int Max=1000000;
 6 using namespace std;
 7 
 8 int n,cnt,aa,bb;
 9 int visited[N];
10 int head[N];
11 int dist[N];
12 
13 struct Edge{
14     int v,w,next;
15 }edge[N*4];
16 
17 void CreateMap(int u,int v,int w){
18     edge[cnt].v=v;
19     edge[cnt].w=w;
20     edge[cnt].next=head[u];
21     head[u]=cnt++;
22 }
23 
24 void SPFA(){
25     memset(visited,0,sizeof(visited));
26     memset(dist,-1*Max,sizeof(dist));
27     queue<int>Q;
28     Q.push(aa);
29     dist[aa]=0,visited[aa]=1;
30     while(!Q.empty()){
31         int v=Q.front();
32         Q.pop();
33         visited[v]=0;
34         for(int i=head[v];i!=-1;i=edge[i].next){
35             if(dist[edge[i].v]<dist[v]+edge[i].w){
36                 dist[edge[i].v]=dist[v]+edge[i].w;
37                 if(!visited[edge[i].v]){
38                     Q.push(edge[i].v);
39                     visited[edge[i].v]=1;
40                 }
41             }
42         }
43         //visited[v]=1;加了这个条件就WA了;
44     }
45 }
46 
47 int main(){
48     while(scanf("%d",&n)!=EOF){
49         memset(head,-1,sizeof(head));
50         int u,v,w;
51          aa=Max,bb=0,cnt=0;
52         for(int i=1;i<=n;i++){
53             scanf("%d%d%d",&u,&v,&w);
54             if(u<aa)aa=u;
55             if(v>bb-1)bb=v+1;
56             CreateMap(u,v+1,w);
57         }
58         for(int i=aa;i<=bb;i++){
59             CreateMap(i,i-1,-1);   //题目中的隐含条件： 0<=f(a)-f(a-1)<=1;转化为f(a-1)>=f(a)+(-1)&&f(a)>=f(a-1)+0;
60             CreateMap(i-1,i,0);
61         }
62         SPFA();
63         printf("%d\n",dist[bb]);
64     }
65     return 0;
66 }

由于求的是最小值，因此要求最长路。。。。即要满足(dist[v]>dist[u]+edge[u][v])。。。

如果求的是最大值，那么就要求最短路，即要满足（dist[v]<dist[u]+edge[u][v]);