正如上文所言，图论的「精髓」就在「转化」了。把一个纯粹的数学问题转换成为可以用图表示的问题，然后通过求解路径（最小值？最大值？），得解。听起来很美。
以本题为例。给出每个军营的最大容量，给出从军营i到军营j最少的人数，求总人数的最小值。
这就是典型的差分约束了。有“分”，有“约束”，至于为什么叫“差”，我想大致是因为首先把Ai + .... + Aj写成S[j] - S[i - 1]（和之差）的形式吧。btw，这种转换似乎是很常见的处理方法。
好吧，看上去和图论八竿子搭不上边。以题目给的第一组数据为例。
3 2
1000 2000 1000
1 2 1100
2 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;
}
评论