POJ 1201-Intervals(差分约束系统)-白红宇

POJ 1201-Intervals(差分约束系统)

阅读量：6258 次

发布时间：2019-06-22

本文共 1128 字，大约阅读时间需要 3 分钟。

题目地址:

题意：构造一个集合，这个集合内的数字满足所给的n个条件。每一个条件都是指在[a,b]内至少有c个数在集合内。问集合最少包括多少个点。即求至少有多少个元素在区间[a,b]内。

思路：

对于题目中所说的每一个条件[a,b]内至少有c个数在集合能够表示为dis(b+1)-dis(a)>=c,能够看出是求最长路

然后题目中存在着隐藏条件。

dis表示的是在[0,i-1]的范围内，要选多少个数。数列dis是递增的，可是增量最大是1。也就是说0<=dis(i)-dis(i-1)<=1，这个式子等价于dis(i)-dis(i-1)<=1和dis(i-1)-dis(i)<=0

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const double pi= acos(-1.0);const double esp=1e-6;const int MAXN=50010;int head[MAXN],vis[MAXN],dis[MAXN];int cnt;struct node{ int v,w; int next;}edge[1000010];void add(int u,int v,int w){ edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++;}void SPFA(int s){ int i; memset(dis,-inf,sizeof(dis)); memset(vis,0,sizeof(vis)); queue
                
                 q; dis[s]=0; vis[s]=1; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(dis[v]

转载于:https://www.cnblogs.com/yutingliuyl/p/7047434.html

你可能感兴趣的文章