poj2983（差分约束系统） - c++编程基础

题意：一天南北线上有n个防御站，给出他们之间的位置关系，问有没有可能存在这样一种位置布置符合所给的位置关系。关系有两种，一种是 P A B X，表示A在B北边X光年的位置，V A B表示A在B北边至少1光年位置。

解法：查分约束。dist[A]-dist[B]>=X,表示A在B北边至少X光年位置。变形为：dist[B]<=dist[A]-X;所以A指向B有条权值为-X的边。这也是最短路松弛原理的关系。对于A-B=X，则建两条边dist[B]<=dist[A]-X，dist[A]<=dist[B]+X。

SPFA时候如果存在负权环则说明不符合实际情况。

代码：

/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, /STACK:102400000,102400000)
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include
           #include 
           
             #include 
            
              #include 
             
               //freopen (in.txt , r , stdin); using namespace std; #define eps 1e-8 #define zero(_) (abs(_)<=eps) const double pi=acos(-1.0); typedef long long LL; const int Max=1010; const LL INF=0x3FFFFFFF; struct point { int u; int dist; }; vector
              
                vec[Max]; int dis[Max]; int que[Max*Max]; int rem[Max]; int n,m; bool spfa1() { memset(dis,0x3f,sizeof dis); memset(rem,0,sizeof rem); que[0]=0; int left=0,right=1; dis[0]=0; while(left
               
                dis[t]+vec[t][i].dist) { dis[vec[t][i].u]=dis[t]+vec[t][i].dist; que[right++]=vec[t][i].u; rem[vec[t][i].u]++; if(rem[vec[t][i].u]>n+2) return false; } } } return true; } int main() { while(scanf(%d%d,&n,&m)==2) { vec[0].clear(); for(int i=1; i<=n; i++) { vec[i].clear(); point p; p.u=i; p.dist=1; vec[0].push_back(p); } bool flag=1; for(int i=0; i
                
                 ?