poj-3169Layout

时间:2024-07-14 09:37:26

题意

当排队等候喂食时,奶牛喜欢和它们的朋友站得靠近些。FJ有N(2<=N<=1000)头奶牛,编号从1到N,沿一条直线站着等候喂食。奶牛排在队伍中的顺序和它们的编号是相同的。因为奶牛相当苗条,所以可能有两头或者更多奶牛站在同一位置上。即使说,如果我们想象奶牛是站在一条数轴上的话,允许有两头或更多奶牛拥有相同的横坐标。
一些奶牛相互间存有好感,它们希望两者之间的距离不超过一个给定的数L。另一方面,一些奶牛相互间非常反感,它们希望两者间的距离不小于一个给定的数D。给出ML条关于两头奶牛间有好感的描述,再给出MD条关于两头奶牛间存有反感的描述。(1<=ML,MD<=10000,1<=L,D<=1000000)
你的工作是:如果不存在满足要求的方案,输出-1;如果1号奶牛和N号
奶牛间的距离可以任意大,输出-2;否则,计算出在满足所有要求的情况下,1号奶牛和N号奶牛间可能的最大距离。


题解

差分约束,第一种A向B连权值为v的边,第二种B向A连-v的边。
SPFA当有环时,-2;跑不到n, -1 我打的是DFS


常数巨大的丑陋代码

# include <stdio.h>
# include <stdlib.h>
# include <iostream>
# include <string.h>
# include <math.h>
# define RG register
# define IL inline
# define ll long long
# define mem(a, b) memset(a, b, sizeof(a))
# define Min(a, b) (((a) > (b)) ? (b) : (a))
# define Max(a, b) (((a) < (b)) ? (b) : (a))
using namespace std; IL int Get(){
RG char c = '!'; RG int x = 0, z = 1;
for(; c > '9' || c < '0'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c <= '9' && c >= '0'; c = getchar()) x = x * 10 + c - '0';
return x * z;
} const int MAXN = 1001, MAXM = 20001, INF = 2147483647;
int n, dis[MAXN], vis[MAXN], ft[MAXN], m1, cnt, m2, flag;
struct Edge{
int to, f, nt;
} edge[MAXM]; IL void Add(RG int u, RG int v, RG int f){
edge[cnt] = (Edge){v, f, ft[u]}; ft[u] = cnt++;
} IL void Dfs(RG int u){
vis[u] = 1;
if(flag) return;
for(RG int e = ft[u]; e != -1; e = edge[e].nt){
RG int v = edge[e].to, f = edge[e].f + dis[u];
if(dis[v] > f){
dis[v] = f;
if(vis[v]){
flag = 1;
return;
}
Dfs(v);
}
}
vis[u] = 0;
} int main(){
mem(dis, 63); mem(ft, -1);
n = Get(); m1 = Get(); m2 = Get();
for(RG int i = 1; i <= m1; i++){
RG int u = Get(), v = Get(), f = Get();
Add(u, v, f);
}
for(RG int i = 1; i <= m2; i++){
RG int u = Get(), v = Get(), f = Get();
Add(v, u, -f);
}
dis[1] = 0; Dfs(1);
if(flag) printf("-1\n");
else if(dis[n] == dis[0]) printf("-2\n");
else printf("%d\n", abs(dis[n]));
return 0;
}

相关文章