博文
Zju 1508 Intervals(2006-12-15 14:22:00)
摘要： 差分约束的入门题。比2770稍复杂，需要稍微转化一下。
设S[i]是前i个数中选出的个数，则ai到bi的个数即S[bi] - S[ai-1]。因此有S[bi] - S[ai-1] >= ci。另外有S[i] - s[i - 1] >= 0 && S[i] - S[i - 1] <= 1，故建图。
使图中每一组uv，满足
S[ai - 1] <= S[bi] + ci
S[i] <= S[i - 1] + 1
S[i - 1] <= S[i]
当不满足时，更新即可。
tips：因为此题必有解（题给出），因此bellmanford只需更新至全部满足即可。
#include <cstdio>
#include <string>
#define inf 99999
struct Edge
{
int u, v, w;
} edge[50001];
int n, a[50001], mn, mx;
void init()
{
int i;
for(i = 0; i < 50001; i ++)
a[i] = 0;
mx = 1, a[0] = 0, mn = inf;
}
bool bellman_ford()
{
int i, t, f = 1;
// pa();
// must satisfy following aspects:
// s[v] <= s[u] - w
// s[i] <= s[i - 1] + 1
// s[i - 1] <= s[i]
while(f)
{
f = 0;
for(i = 0; i &l......
Zju 2770 Burn the Linked Camp（2）(2006-12-11 21:43:00)
摘要： 正如上文所言，图论的「精髓」就在「转化」了。把一个纯粹的数学问题转换成为可以用图表示的问题，然后通过求解路径（最小值？最大值？），得解。听起来很美。
以本题为例。给出每个军营的最大容量，给出从军营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 > -20......
Zju 2770 Burn the Linked Camp（1）(2006-12-11 17:42:00)
摘要：
2168048
2006-12-11 16:57:17
Accepted
2770
C++
00:00.59
676K
Crux.D
图论是一种美妙的东西。虽然不能化粪土为金钱，但是很多看上去不可能的任务可以用简单的转换完成。当然，其中的奥妙就在于「转换」二字。
因此，为了顺利完成从菜鸟成长为大菜鸟的计划，我决定学习进阶图论。
---------------BVB养成计画·第一话 BellmanFord-------------------
BellmanFord是一种计算最短路径的算法。虽然之前学过相当多的最短路径，如Dijkstra算法，Floyd算法，但他们是有适用范围的。即两算法下边的权值不能为负。因为考虑以下情况：
出点 入点 权值
1 2 -3
2 3 -2
3 1 2
这样即构成了一条从1点到3点的负值回路-3 + -2 + 2 = -3，这样永远算不出1到3的最短路径了（因为可以无限循环-3 -6 -9....）。
所以BF算法是专门提出来解决上述问题的－－计算每个点对源点s的最短路径。
算法的伪代码如下
BF(G,w,s)
// 假设一张图G，从源点s出发，每条u至v的边权值为w(u,v)，共有n格点。
Determine Single Source(G,......