正如上文所言，图论的「精髓」就在「转化」了。把一个纯粹的数学问题转换成为可以用图表示的问题，然后通过求解路径（最小值？最大值？），得解。听起来很美。 以本题为例。给出每个军营的最大容量，给出从军营i到军营j最少的人数，求总人数的最小值。 这就是典型的差分约束了。有“分”，有“约束”，至于为什么叫“差”，我想大致是因为首先把Ai + .... + Aj写成S[j] - S[i - 1]（和之差）的形式吧。btw，这种转换似乎是很常见的处理方法。 好吧，看上去和图论八竿子搭不上边。以题目给的第一组数据为例。 3 21000 2000 10001 2 11002 3 1300 我们可以得到如下关系式。（= 省略，下同） A1 < 1000, A2 < 2000, A3 < 1000; S2 - S0 > 1100, S3 - S1 > 1300; 第一组不等式又可写作 S1 - S0 < 1000, S2 - S1 < 2000, S3 - S2 < 1000 好吧.....不很明显，再改一下： S0 - S1 > -1000, S1 - S2 > -2000, S2 - S3 > -1000 全部改成>后，回到上文中最后一个结论Distance(v) < Distance(u) + w(u,v)。即D(u) - D(v) > -w(u,v)。 把D改成S，是不是很像？......很牵强吧。 但毕竟还是有相同的地方。比如离散数学里的传递性：S0 - S1 > -1000, S1 - S2 > -2000, 那么，S0 - S2 > -3000。这就和图的路径奇妙地构成映射了。把每个S看作一个点，从前者向后者引出一条边，以差为负权值(-w(u,v))。这就是图了。 现在我们就有了一组已知量（5条边）-w(u, v)，一组未知量 D0,D1,D2，3个点。这里Di代表的是点i到点3的距离....我的写法总是和标准差那么一点，更规范的写法是到点0的距离。显然，D3为0。这样就转化成了已知边求最短路径（S3－S0）。 回到问题。现在有五组不等式，要求的是在满足不等式的前提下S3 - S0的最小值。所谓最小值，其实所有满足不等式的D3的最大值；由于边为负，恰巧变成了最短路径。 当然这只会WA。刘备的兵营没有出现幽灵事件，Ai > 0。而且i到j是有上限的，不能比所有Ai到Aj的和更多。所以刚好是两组对称的不等式。世界是平衡的，不会有绝对的善和恶。 代码不是很长，大概是Bellman很偷懒的缘故。 #include <cstdio>#include <string> #define mx 9999999 int n, m, a[1001], ei, c[1001], d[1001]; struct Edge{ int u, v, w;} edge[23000]; void init(){ ei = 0; int i; for(i = 0; i <= n; i ++) a[i] = mx; d[0] = 0; a[n] = 0;} bool bellman_ford(){ int i, k, t; for(i = 0; i < n; i ++) { for(k = 0; k < ei; k ++) { t = a[edge[k].u] + edge[k].w; if(a[edge[k].u] != mx && t < a[edge[k].v]) { a[edge[k].v] = t; } } //pa(); } for(k = 0; k < ei; k ++) { if(a[edge[k].u] != mx && a[edge[k].u] + edge[k].w < a[edge[k].v]) { return false; } } return true;} int main(){ //freopen("in.txt", "r", stdin); while(scanf("%d %d", &n, &m) != EOF) { init(); int i, u, v, w; for(i = 1; i <= n; i ++) { scanf("%d", &c[i]); edge[ei].u = i - 1; //out edge[ei].v = i; //in edge[ei].w = c[i]; ei ++; edge[ei].u = i; edge[ei].v = i - 1; edge[ei].w = 0; ei ++; d[i] = c[i] + d[i - 1]; } for(i = 0; i < m; i ++) { scanf("%d %d %d", &u, &v, &w); //f(k) - f(t - 1) >= -j edge[ei].u = v; edge[ei].v = u - 1; edge[ei].w = -w; ei ++; //f(k) - f(t - 1) <= c[t] + ... + c[k] == (d[k] - d[t - 1]) edge[ei].u = u - 1; edge[ei].v = v; edge[ei].w = d[v] - d[u - 1]; ei ++; } //pe(); if(!bellman_ford()) printf("Bad Estimations\n"); else printf("%d\n", a[n] - a[0]); } return 0;}
评论