洛谷 1260 工程规划（差分约束）-白红宇

洛谷 1260 工程规划（差分约束）

阅读量：4969 次

发布时间：2019-06-12

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

/*Ti≤Tj+b意味Ti的最大值为Tj+b；Tj≥Ti-b意味Tj的最大值为Ti-b；因此，根据题中给出的m个不等式，逐步调整各个Ti的最小值和最大值。设high[i]为Ti当前的最大值，low[i]为Ti当前的最小值。high[j]为Tj当前的最大值，low[j]为Tj当前的最小值。若high[i]-high[j]>b，则high[i]=high[j]+b(根据Ti≤Tj+b)，若low[i]-low[j]
     
      #include
      
       #include
       
        #define maxn 5010using namespace std;int n,m,l[maxn],r[maxn],x[maxn],y[maxn],z[maxn],can;void Get_lr(){    for(int i=2;i<=n;i++)      l[i]=-100000,r[i]=100000;//绝对值不够大不行 不是简单地 -100 - 100                                //每两个是100 一共1000个 1000*100 }int main(){    scanf("%d%d",&n,&m);    Get_lr();    for(int i=1;i<=m;i++)      scanf("%d%d%d",&x[i],&y[i],&z[i]);    while(1)      {          int falg=0,f=0;          for(int i=1;i<=m;i++)            {                if(r[x[i]]>r[y[i]]+z[i])              r[x[i]]=r[y[i]]+z[i],f++;                if(l[y[i]]
        
         r[i])            {              falg=1;break;            }        if(falg)break;        if(f==0)          {              can=1;break;          }      }    if(!can)      {          printf("NO SOLUTION\n");          return 0;      }    int cd=0x3f3f3f3f;    for(int i=1;i<=n;i++)cd=min(cd,l[i]);//调整结果 恰好有零     for(int i=1;i<=n;i++)printf("%d\n",l[i]-cd);    return 0;}