|
|
思路：
差分约束是个很神奇的东西，能将下面这种类型的不等式约束问题：
d[1] - d[2] <= a
d[4] - d[7] <= b
...
求 d[x] 的最大/小值
转化为最短路径的问题，真吗的太牛逼了。
原理呢，就是一个图求出单源最短路径之后。
两点之间的关系必然是满足 d[u] + w[u,v] >= d[v] 的，没法再松弛了。
对于这道题，有两种约束： 1. 输入里指明的约束 2. d[1] <= d[2] <= d[3] .... <= d[N] 建立完这两种约束之后，然后spfa求一下最短路径。 如果有负环，就输出 -1 如果不连通，就输出 -2
 #include <stdio.h>
#define MAX_DIS 1000000032
#define MAX_N 1024
#define MAX_EDGES 65536
  struct edge_node  {
 int i, w;
struct edge_node *next;
 };
int N, ML, MD;
struct edge_node edges[MAX_EDGES], *map[MAX_N];
int edges_cnt;
int D[MAX_N], queue[MAX_N], head, tail, vis[MAX_N], tm, cnt[MAX_N];
inline void add_edge(int a, int b, int w)
{
struct edge_node *e = &edges[edges_cnt++];
e->i = b;
e->w = w;
e->next = map[a];
map[a] = e;
}
inline int push(int i, int d)
{
if (d >= D[i])
return 0;
D[i] = d;
if (vis[i] == tm)
return 0;
vis[i] = tm;
cnt[i]++;
if (cnt[i] >= N)
return 1;
queue[tail++] = i;
tail &= MAX_N - 1;
return 0;
}
inline int spfa()
{
int i;
struct edge_node *e;
for (i = 1; i <= N; i++)
D[i] = MAX_DIS;
tm++;
head = tail = 0;
push(1, 0);
  while (head != tail) {
i = queue[head++];
head &= MAX_N - 1;
vis[i] = 0;
for (e = map[i]; e; e = e->next)
if (push(e->i, D[i] + e->w))
return 1;
 }
return 0;
}
int main()
{
int a, b, w, i;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d%d", &N, &ML, &MD);
while (ML--) {
scanf("%d%d%d", &a, &b, &w);
add_edge(a, b, w);
}
while (MD--) {
scanf("%d%d%d", &a, &b, &w);
add_edge(b, a, -w);
}
for (i = 2; i <= N; i++)
add_edge(i, i - 1, 0);
if (spfa())
a = -1;
else
a = (D[N] == MAX_DIS) ? -2 : D[N];
printf("%d\n", a);
return 0;
}
|