编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 931ms

├ 测试数据 06：答案正确... 88ms

├ 测试数据 07：答案正确... 275ms

├ 测试数据 08：答案正确... 56ms

├ 测试数据 09：答案正确... 72ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1422m

汗……

我是不是bellman ford不会写了？！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 197ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 25ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：222ms

puppy上也很慢……

谁AC了 给我一个bellman-ford版本的让我参考下……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

只存b+1->a的边存值为c ([a,b])

然后在bellman时,对于d[i]>d和d[i]-1>d(即针对s[i]-s>=0跟s-s[i]>=-1这两个约束条件)情况进行更新,这样可以避免存太多的边,而且速度更快~0~...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 88ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 119ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：207ms

这感觉真好。。半个下午的努力。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

bellman-ford

差分约束系统

我用指针存的边、、SPFA最大路径、、

G:=0;G:=-1;

为什么第9个点老是错、、、

我加了个弱弱的线段树才秒杀

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 212ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 352ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：564ms

邻接表SPFA照样过。。。。。。

贪心直接秒杀。。。。

邻接表SPFA的速度：

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 103ms

├ 测试数据 06：答案正确... 103ms

├ 测试数据 07：答案正确... 775ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：运行超时...

├ 测试数据 10：答案正确... 0ms

前向星SPFA的速度：

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 40ms

├ 测试数据 06：答案正确... 72ms

├ 测试数据 07：答案正确... 228ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 508ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：857ms

我的代码能力很弱，时间很丑，但希望用血的事实证明：要用前向星！

差分约束。。就这样= =

貌似贪心也能A...囧

介绍下差分约束的做法：

现在考虑这样的问题：若要求某数是定值x，且这个数在图中到任意点有路径，求除了这个值以外其他所有值最大，如何做呢？以该点为S，求最短路，然后每个点加x即可。如果要求所有值最小，则把不等式变化为>=然后求最长路。

证明：以求最大值为例，可以证明必定存在一个解集M使得除了定值（设定值为0）以外的解都可以达到最大值。设最短路求出来的解集合为D，考虑这个解集，对于任意的Xi必定>=Di，故若以M为初始值进行BF算法的话可以得到D，但是由于M中所有的值都满足三角不等式，所以BF算法不会对M集进行松弛，换句话说，M=D，证毕。

数组开小了，弄了2个星期

注意，数组不够显示答案错误

差分约束系统

用bellman-ford很快啊！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

Accepted 有效得分：100 有效耗时：9ms

早上兴致勃勃地写了个SPFA的差分约束系统，20分…………#%￥@#%￥……&

换成Bellman_Ford就AC了，而且效率不低……大牛们能不能告诉我为什么呢？？

06年冯威的论文貌似有点儿问题..

自己想了下写过了.

差分约束..

查分约束系统。

如果(a,b)之间至少有c个数，则s-s[a-1]>=s。

然后还有一些隐含的：

s-s[i]>=0

s[i]-s>=-1

再固定s[0]为0，建成一张图，做一遍SPFA（求最长路径），然后取距离最大值。

终于学会差分约束系统了！用BELLMAN-FORD就可以了。

看数据范围...前向星+spfa.

Orz楼下两位大牛.