题解 P1993 【小K的农场】

蒟蒻刚学差分约束……~~拿道模板题练练手。~~ 先稍微说一下我理解的差分约束系统吧……它的原理就是，在图上用x->y的边权c表示v(x)-v(y)>=c（或小于等于）。 对于多个不等式组: v(x1) - v(x2) >= c1 v(x2) - v(x3) >= c2 …… 把它们**加起来**就会得到:v(x1) - v(xn) >= c1 + c2 + …… + cn-1 实际上上面的不等式组恰好**可以看成一条路径，每个不等式即路径上的一小段**。（路径总长等于每段路径长度之和） 所以按照上面所说的方式建图，实际上这个图包含了任意约束条件相加的结果（条件是，这个结果必须是v(x)-v(y)>=c的形式，不能有v(z)之类多出来的项）。 对于求差分的最小值嘛，我们当然希望不等式的方向是大于等于，这样就有了最小值，毕竟**如果a>=1是唯一的条件，a最小就是1**。（最大值也是同理） 我们求v(x) - v(y)的最小值，实际上是求众多的诸如此类的不等式中c值最大的一个： v(x) - v(y) >= c1 v(x) - v(y) >= c2 …… 为什么呢？因为这些不等式既然是由已知约束所累加起来的，自然都是必须被满足的。而如果满足了最大的c，那么所有的c都能被满足。所以求解最小值其实是要找到最大值（即约束**最严苛**的一个不等式） 所以求v(x)-v(y)的**最小值**是在图上求**最长路径**。这乍看上去似乎有些不合理（毕竟想要最小却去找最大，怪怪的）。 好了，开始讲讲具体怎么做这道题。 对于a-b>=c，个人比较习惯连一条a到b，权值为c的边，实际上也是这么做的…… 以下是处理输入的方法： 1,a,b,c -> a-b>=c，连a->b权值为c的边 2,a,b,c -> a-b<=c，即b-a>=-c，连b->a权值为-c的边 3,a,b -> a-b>=0，且b-a>=0，即在a，b间接双向边，边权都为0 但是对于整个系统来说，还有一些额外的约束，即任意一个农场种的作物的单位数都为正值（回想起来**好像并不会影响结果**……就当严谨起见吧） 对于这个这个约束条件，我们开额外的一个节点（农场），标号为0且作物单位也认为是0，对于[1,n]内的点都连一条x->0，边权为0的边(即x-0>=0) 然后我们来考虑什么情况差分约束系统无解。 先考虑要求v(x)-v(0)的最大值还是最小值(由于接到了0号农场，v(n)-v(0)即v(n),v(x)为农场x的作物数)。 当然是求最小值啦！我们的不等式全都是大于等于，哪来的最大值…… 要求最小值，就是要求约束最苛刻的一个值，也就是求最大路径（前面提到过了） 所以我们就去求最大路径。**如果某个点到0号点的最大路径不存在，那就无解了**。 就是求**正权环**啦！！（~~可惜标签只有负权环2333~~） 怎么求正权环……如果你想利用Floyd顺手得到正权环，emmm，TLE等着你。(O(n^3)) 但这个图是不连通的啊，如果SPFA判环，搞不好就WA了。 所以我们要让他连通：再新增一个点n+1,它对[1,n]的点都连上一条边权为0的边。 注意这些边其实是**没有意义**的（没有v(n+1)-v(x)>=0的意思），只是为了判断任意一个点v(x)-v(0)是否有最小值。 于是我老老实实地写了个朴素的SPFA，结果四个点被卡TLE了。。（感到了出数据者深深的恶意） 所以需要用**dfs优化的SPFA**，这个小东西很容易想（我看到这个名称后**靠灵性**写出代码了……）。具体看代码吧，会有注释的。 顺便一提，如果你想用邻接表（通常都是这么存图的吧？）存图，对于差分约束系统来说，**建议先无脑比题目中的点数多开个十来倍**，因为差分约束系统经常会需要增加一些奇奇怪怪的条件（比如>=0）和辅助边，**经常加新边后忘了该数组大小**……先开够，更安全一下。 ```cpp #include <cstdio> #include <cstdlib> #define FOR_EDGE(i,pt) for (int i(iHead[pt]); i; i = all[i].next) class edge { public: int to, val, next; }all[112345]; int iHead[11234]; int iEnd(2); void add(int fr, int to, int val) { all[iEnd].to = to; all[iEnd].val = val; all[iEnd].next = iHead[fr]; iHead[fr] = iEnd++; } int n, m; bool bInQue[11234], vis[11234];//bInQue表示这个点当前正在被dfs，vis表示这个点被访问过了（也就是说len值已经有效了） int len[11234];//最长距离 bool SPFA(int now) { bInQue[now] = true;//访问标记 FOR_EDGE(i, now) { if (!vis[all[i].to] || len[all[i].to] < len[now] + all[i].val) { if (bInQue[all[i].to]) return false;//如果一个点通过一段路径后回到了自己且这段路径还比之前的优，意即存在所寻找的环，返回 vis[all[i].to] = true; len[all[i].to] = len[now] + all[i].val; if (!SPFA(all[i].to)) return false;//存在一个正权环就够说明问题了，一路返回 } } bInQue[now] = false; return true;//还没找到正权环 } int main() { scanf("%d%d", &n, &m); for (int i(1); i <= n; ++i) { add(i, 0, 0); add(n + 1, i, 0); } for (int i(0); i != m; ++i) { int cmd, a, b, c; scanf("%d", &cmd); switch (cmd) { case 1: scanf("%d%d%d", &a, &b, &c); add(a, b, c); break; case 2: scanf("%d%d%d", &a, &b, &c); add(b, a, -c); break; case 3: scanf("%d%d", &a, &b); add(a, b, 0); add(b, a, 0); break; } } if (SPFA(n + 1)) { printf("Yes\n"); } else { printf("No\n"); } return 0; } ```