POJ 1201 Intervals-白红宇

POJ 1201 Intervals

阅读量：6760 次

发布时间：2019-06-26

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

差分约束

题意倒是简单。难的是建立约束（建边）。能够初始化INF求最小。然后输出-dis[maxn]。也能够初始化-INF求最大，输出dis[maxn]。

求最大的时候：

minn为最小。maxn为最大。

输入 u ,v len 建立约束为 u->v = len。最后在 minn和maxn之间还要建立 i->i-1=-1 , i-1->i=0。

最后求minn-1 ~maxn 的最大距离。

求最小就是建边不变，距离变负。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #define INF 0x7fffffff#define eps 1e-6#define LL long longusing namespace std;int n,maxn,minn,m;struct lx{ int v,len;};vector
                
                 g[51001];queue
                 
                  q;void SPFA(){ bool vis[51001]; int dis[51001]; for(int i=0;i<=maxn;i++) vis[i]=0,dis[i]=-INF; vis[minn-1]=1,dis[minn-1]=0; q.push(minn-1); while(!q.empty()) { int u=q.front();q.pop(); vis[u]=0; for(int j=0;j
                  
                   %d+%d=\n",v,u,dis[v],dis[u],len);// system("pause"); if(dis[v]
                   
                     ",i);// for(int j=0;j