文章目录
R
e
s
u
l
t
Result
Result
H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
D
e
s
c
r
i
p
t
i
o
n
Description
Description
S
o
l
u
t
i
o
n
Solution
Solution
C
o
d
e
Code
Code
R
e
s
u
l
t
Result
Result
H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
https://www.luogu.com.cn/problem/P4878
D
e
s
c
r
i
p
t
i
o
n
Description
Description
有
n
n
n个未知数，给定
m
1
+
m
2
m1+m2
m1+m2组限制条件，前
m
1
m1
m1个条件要求满足
a
i
−
a
j
≤
D
a_i-a_j\leq D
ai−aj≤D，后
m
2
m2
m2个条件要求满足
a
i
−
a
j
≥
D
a_i-a_j\geq D
ai−aj≥D 求一组非负整数解，使得
a
n
−
a
1
a_n-a_1
an−a1最大 若此数无穷大，输出-2；若有负环，输出-1
数据范围：
n
≤
1
0
3
,
m
1
+
m
2
≤
2
×
1
0
4
n\leq 10^3,m_1+m_2\leq 2\times 10^4
n≤103,m1+m2≤2×104
S
o
l
u
t
i
o
n
Solution
Solution
显然是一道负环差分约束 由于我们要求的是上界，所以要用最短路 建边
(
0
,
i
,
0
)
(0,i,0)
(0,i,0)，
d
i
s
i
≥
d
i
s
0
=
0
dis_i\geq dis_0=0
disi≥dis0=0即每个数都非负 对于前
m
1
m_1
m1个限制条件，建边
(
a
,
b
,
c
)
(a,b,c)
(a,b,c)，表示
d
i
s
b
≤
d
i
s
a
+
c
dis_b\leq dis_a+c
disb≤disa+c即
d
i
s
b
−
d
i
s
a
≤
c
dis_b-dis_a\leq c
disb−disa≤c 对于后
m
2
m_2
m2个限制条件，建边
(
b
,
a
,
−
c
)
(b,a,-c)
(b,a,−c)，表示
d
i
s
a
≤
d
i
s
b
−
c
dis_a\leq dis_b-c
disa≤disb−c即
d
i
s
b
≥
d
i
s
a
+
c
dis_b\geq dis_a+c
disb≥disa+c
然后必须先从
0
0
0开始跑一遍，因为图不一定是联通的
C
o
d
e
Code
Code
#include<queue>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std
;int n
,m1
,m2
,dis
[5010],tot
,l
[5010],in
[5010],a
,b
,c
;
bool vis
[5010];
struct node
{int next
,to
,w
;}e
[40010];
inline void add(int u
,int v
,int w
){e
[++tot
]=(node
){l
[u
],v
,w
};l
[u
]=tot
;return;}
queue
<int>q
;
inline LL
read()
{
char c
;LL d
=1,f
=0;
while(c
=getchar(),!isdigit(c
)) if(c
=='-') d
=-1;f
=(f
<<3)+(f
<<1)+c
-48;
while(c
=getchar(),isdigit(c
)) f
=(f
<<3)+(f
<<1)+c
-48;
return d
*f
;
}
inline bool spfa(int s
)
{
memset(dis
,0x3f,sizeof(dis
));
memset(vis
,0,sizeof(vis
));
memset(in
,0,sizeof(in
));
vis
[s
]=true;dis
[s
]=0;in
[s
]=1;
q
.push(s
);
while(q
.size())
{
int u
=q
.front();q
.pop();
for(register int i
=l
[u
];i
;i
=e
[i
].next
)
{
int v
=e
[i
].to
,w
=e
[i
].w
;
if(dis
[v
]>dis
[u
]+w
)
{
dis
[v
]=dis
[u
]+w
;
if(vis
[v
]==0) {vis
[v
]=1;q
.push(v
);in
[v
]++;if(in
[v
]>n
+1) return true;}
}
}vis
[u
]=false;
}
return false;
}
signed main()
{
n
=read();m1
=read();m2
=read();
for(register int i
=n
;i
;i
--) add(0,i
,0);
for(register int i
=1;i
<=m1
;i
++) a
=read(),b
=read(),c
=read(),add(a
,b
,c
);
for(register int i
=1;i
<=m2
;i
++) a
=read(),b
=read(),c
=read(),add(b
,a
,-c
);
if(spfa(0)+spfa(1)>0) puts("-1");
else printf("%d",dis
[n
]==0x3f3f3f3f?-2:dis
[n
]);
}
