考察:差分约束
错误思路:
设di 为 第i头牛的坐标, 由题可以得到 dB - dA <= L . dB - dA >= D . 两边减少d1 ,设f[i] = di - d1 , 答案是求f[n]的最大值.
这样确实可以建边,但是找不到源点.1不能保证到所有的点.如果用 di-1 <= di 的话1是所有点的终点,也不能成立.
反过来考虑减少dn 这样求的是f[1]的最小值. 和上面一样找不到源点.
思路:
我们由题目可以发现 每个式子都是相对关系,如果求最值我们需要绝对关系.
这里考虑假设所有点di <= 0. 那么超级源点就是d0 = 0. 先考虑第一问,如果不存在可行解说明存在负(正)环,这时跑最短(长)路即可.
第二问,因为我们求的是1与n的相对距离,假设1的坐标为0, 那么再计算n的坐标,如果n无法到达就是取任意值,否则跑最短路.
1 #include <iostream>
2 #include <cstring>
3 #include <queue>
4 #include <stack>
5 using namespace std;
6 typedef long long LL;
7 const int N = 1010,M = 20010,INF = 0x3f3f3f3f;
8 int h[N],m1,m2,n,idx,cnt[N];
9 LL dist[N];
10 bool st[N];
11 struct Road{
12 int fr,to,ne,w;
13 }road[M];
14 void add(int a,int b,int c)
15 {
16 road[idx].w = c,road[idx].fr = a,road[idx].to = b,road[idx].ne = h[a],h[a] = idx++;
17 }
18 bool spfa_judge()
19 {
20 stack<int> q;
21 for(int i=1;i<=n;i++) q.push(i),st[i] = 1;
22 while(q.size())
23 {
24 int u = q.top();
25 q.pop();
26 st[u] = 0;
27 for(int i=h[u];~i;i=road[i].ne)
28 {
29 int v = road[i].to;
30 if(dist[v]>dist[u]+road[i].w)
31 {
32 dist[v] = dist[u]+road[i].w;
33 cnt[v] = cnt[u]+1;
34 if(cnt[v]>=n) return 0;
35 if(!st[v]) q.push(v),st[v] = 1;
36 }
37 }
38 }
39 return 1;
40 }
41 LL spfa()
42 {
43 queue<int> q;
44 for(int i=1;i<=n;i++) dist[i] = INF;
45 q.push(1); st[1] = 1;
46 dist[1] = 0;
47 while(q.size())
48 {
49 int u = q.front();
50 q.pop();
51 st[u] = 0;
52 for(int i=h[u];~i;i=road[i].ne)
53 {
54 int v = road[i].to;
55 if(dist[v]>dist[u]+road[i].w)
56 {
57 dist[v] = dist[u]+road[i].w;
58 if(!st[v]) q.push(v),st[v] = 1;
59 }
60 }
61 }
62 if(dist[n]==INF) return -2;
63 else return dist[n];
64 }
65 int main()
66 {
67 scanf("%d%d%d",&n,&m1,&m2);
68 memset(h,-1,sizeof h);
69 while(m1--)
70 {
71 int a,b,l; scanf("%d%d%d",&a,&b,&l);
72 add(a,b,l);
73 }
74 while(m2--)
75 {
76 int a,b,d; scanf("%d%d%d",&a,&b,&d);
77 add(b,a,-d);
78 }
79 for(int i=1;i<=n;i++) add(i,i-1,0);
80 if(spfa_judge()) printf("%lld\n",spfa());
81 else puts("-1");
82 return 0;
83 }