|
|
思路：
差分約束是個很神奇的東西，能將下面這種類型的不等式約束問題：
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;
}
|