P1260 工程规划【洛谷算法习题】

P1260 工程规划

网页链接

P1260 工程规划

题目描述

造一幢大楼是一项艰巨的工程，它是由n nn个子任务构成的，给它们分别编号1 , 2 , ⋯ , n ( 5 ≤ n ≤ 1000 ) 1,2,\cdots,n\ (5≤n≤1000)1,2,⋯,n(5≤n≤1000)。由于对一些任务的起始条件有着严格的限制，所以每个任务的起始时间T 1 , T 2 , ⋯ , T n T_1,T_2,\cdots,T_nT1​,T2​,⋯,Tn​并不是很容易确定的(但这些起始时间都是非负整数，因为它们必须在整个工程开始后启动)。例如：挖掘完成后，紧接着就要打地基；但是混凝土浇筑完成后，却要等待一段时间再去掉模板。

这种要求就可以用m ( 5 ≤ m ≤ 5000 ) m\ (5≤m≤5000)m(5≤m≤5000)个不等式表示，不等式形如T i − T j ≤ b T_i-T_j≤bTi​−Tj​≤b代表i ii和j jj的起始时间必须满足的条件。每个不等式的右边都是一个常数b bb，这些常数可能不相同，但是它们都在区间( − 100 , 100 ) (-100,100)(−100,100)内。

你的任务就是写一个程序，给定像上面那样的不等式，找出一种可能的起始时间序列T 1 , T 2 , ⋯ , T n T_1,T_2,\cdots,T_nT1​,T2​,⋯,Tn​，或者判断问题无解。对于有解的情况，要使最早进行的那个任务和整个工程的起始时间相同，也就是说，T 1 , T 2 , ⋯ , T n T_1,T_2,\cdots,T_nT1​,T2​,⋯,Tn​中至少有一个为0 00。

输入格式

第一行是用空格隔开的两个正整数n nn和m mm，下面的m mm行每行有三个用空格隔开的整数i , j , b i,j,bi,j,b对应着不等式T i − T j ≤ b T_i-T_j≤bTi​−Tj​≤b。

输出格式

如果有可行的方案，那么输出n nn行，每行都有一个非负整数且至少有一个为0 00，按顺序表示每个任务的起始时间。如果没有可行的方案，就输出信息NO SOLUTION。

输入输出样例 #1

输入 #1

5 8 1 2 0 1 5 -1 2 5 1 3 1 5 4 1 4 4 3 -1 5 3 -1 5 4 -3

输出 #1

0 2 5 4 1

输入输出样例 #2

输入 #2

5 5 1 2 -3 1 5 -1 2 5 -1 5 1 -5 4 1 4

输出 #2

NO SOLUTION

说明/提示

由@zhouyonglong提供SPJ

解题思路

本题是差分约束系统的经典应用。给定n nn个变量T 1 , T 2 , … , T n T_1, T_2, \dots, T_nT1​,T2​,…,Tn​，以及m mm个不等式T i − T j ≤ b T_i - T_j \le bTi​−Tj​≤b，要求找出一组非负整数解，且至少有一个变量为0 00。若不存在这样的解，则输出NO SOLUTION。

1. 问题等价转化

• 不等式T i − T j ≤ b T_i - T_j \le bTi​−Tj​≤b可以变形为T i ≤ T j + b T_i \le T_j + bTi​≤Tj​+b。这恰好对应图中一条从节点j jj指向节点i ii的有向边，边权为b bb。
• 因此，整个不等式组构成一个有向图。求解T TT的值等价于在这个图中求最短路径：对于任意一条边j → i j \to ij→i（权值b bb），必须满足T i ≤ T j + b T_i \le T_j + bTi​≤Tj​+b，即T i T_iTi​不超过T j + b T_j + bTj​+b。这正好是三角不等式。
• 如果图中存在负环，则意味着存在矛盾（例如T i ≤ T i + 负数 T_i \le T_i + \text{负数}Ti​≤Ti​+负数），此时无解。
• 由于题目要求T i T_iTi​非负且至少有一个为0 00，我们可以先忽略非负约束，求得任意一组满足不等式的解（可能包含负数），然后找到所有解中的最小值min_val，将每个T i T_iTi​减去min_val，即可得到一组非负解，且最小值为0 00。

2. 算法实现（SPFA 求最短路径）

代码使用SPFA（队列优化的 Bellman-Ford）算法来检测负环并求最短路径。

• 建图：读入m mm个不等式，对于每个T i − T j ≤ b T_i - T_j \le bTi​−Tj​≤b，建立一条从j jj到i ii的有向边，权值为b bb。
• 初始化：由于图可能不连通，需要对每个未访问的节点分别作为起点进行 SPFA。将起点的距离设为0 00，并加入队列。
• SPFA 过程：
  • 从队列中取出节点now，遍历其所有出边。
  • 若dis[to] > dis[now] + w，则更新dis[to]，并将to入队。
  • 使用cnt[now]记录节点入队次数。若某个节点入队次数超过n * n（代码中使用的宽松阈值），则认为存在负环，输出NO SOLUTION并结束。
• 结果处理：
  • 所有节点处理完毕后，dis[i]即为满足不等式组的一组解（可能有负值）。
  • 找出dis[1..n]中的最小值sm。
  • 输出dis[i] - sm，这样所有值都非负，且至少有一个为0 00。

3. 复杂度分析

• 时间复杂度：SPFA 的平均时间复杂度为O ( k m ) O(km)O(km)，其中k kk为常数，最坏情况为O ( n m ) O(nm)O(nm)。本题n ≤ 1000 n \le 1000n≤1000，m ≤ 5000 m \le 5000m≤5000，运算量在可接受范围内。
• 空间复杂度：邻接表存储图需要O ( n + m ) O(n + m)O(n+m)，距离、入队标记等数组需要O ( n ) O(n)O(n)，总空间O ( n + m ) O(n + m)O(n+m)，满足 256M 限制。

总结

将不等式组转化为有向图，利用 SPFA 求最短路径并检测负环。若存在负环则无解；否则得到一组解，再通过整体平移使所有值非负且最小值为0 00。该方法巧妙地将差分约束问题转化为图论最短路问题，是解决此类问题的标准套路。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e5;constll INF=1e9;constll M=1e6+10;constll mod=1e9+7;ll inq[N],dis[N],cnt[N];vector<pll>G[N];queue<ll>Q;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,p,u,v,w;cin>>n>>p;for(ll i=1;i<=p;i++){cin>>u>>v>>w;G[v].push_back({u,w});}for(ll i=1;i<=n;i++)dis[i]=INF;for(ll r=1;r<=n;r++){if(dis[r]!=INF)continue;dis[r]=0;inq[r]=1;Q.push(r);while(!Q.empty()){ll now=Q.front();inq[now]=0;Q.pop();cnt[now]++;if(cnt[now]>=n*n){puts("NO SOLUTION");return0;}for(ll i=0;i<(ll)G[now].size();i++){if(dis[G[now][i].first]>dis[now]+G[now][i].second){dis[G[now][i].first]=dis[now]+G[now][i].second;Q.push(G[now][i].first);inq[G[now][i].first]=1;}}}}ll sm=0;for(ll i=1;i<=n;i++)sm=min(sm,dis[i]);for(ll i=1;i<=n;i++)cout<<dis[i]-sm<<' ';return0;}