洛谷 1260: 工程规划

2018-03-08Chentiancai_nn?

题目描述

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

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

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

输入输出格式

输入格式:

第一行是用空格隔开的两个正整数n和m,下面的m行每行有三个用空格隔开的整数i,j,b对应着不等式Ti-Tj≤b。

输出格式:

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

输入输出样例

输入样例#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:

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

输出样例#2:

NO SOLUTION

说明

由@zhouyonglong提供SPJ

题解

依旧是差分约束系统,我的建图是由$T_i-T_j\leq d$移项后得到$T_i+(-b)\leq T_j$,由$T_i$向$T_j$连一条长为$-b$的有向边跑最大路。

不过本题也是可以写 SPFA-dfs 来求最大路和负环的。 dfs 判负环的原理是每次可以更新 dist 的值时就更新并继续 dfs 下去,如果更新的点已经在路径里了,那么存在负环,不过此题是正环。至于 dist 的问题,初始化为$-inf$,枚举每个点是否开始 dfs ,如果 dist 不为$-inf$,那么是遍历过的,就不用再 dfs 了,如果不是,就设为$0$开始遍历。

当然图上存在都是负权边的情况,那么会有点的 dist 小于$0$,最后还要让所有的 dist 减去最小的 dist 使 dist 值都大于等于$0$

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;
inline void read(int &x){
int f = 1;x = 0;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = x*10+ch-'0';ch = getchar();}
x *= f;
}
const int N = 1005,M = 5005;
int head[N],to[M],nxt[M],w[M],cnt;
int dist[N];
int n,m;
bool vis[N];

inline void insert(int x,int y,int z){ to[++cnt] = y; nxt[cnt] = head[x]; head[x] = cnt; w[cnt] = z; }

void SPFA(int x){
vis[x] = true;
for(int i = head[x];i;i = nxt[i]){
int v = to[i];
if(dist[v] < dist[x]+w[i]){
if(vis[v]){
puts("NO SOLUTION");
exit(0);
}
else{
dist[v] = dist[x]+w[i];
SPFA(v);
}
}
}
vis[x] = false;
}

int main(){
read(n);read(m);
for(int i = 1,x,y,z;i <= m;++i){
read(x); read(y); read(z);
insert(x,y,-z);
}
for(int i = 1;i <= n;++i) dist[i] = -1e9;
for(int i = 1;i <= n;++i){
if(dist[i] == -1e9) dist[i] = 0;
SPFA(i);
}
int Min = 1e9;
for(int i = 1;i <= n;++i) Min = min(Min,dist[i]);
for(int i = 1;i <= n;++i) printf("%d\n", dist[i]-Min);
return 0;
}

检测到你还在使用百度这个搜索引擎,
做为一个程序员,这是一种自暴自弃!

作环保的程序员,从不用百度开始!

Close