【AC_LCC_CWJ 第二场】World Final 2006

这场最后太疼了，都是我个人的原因，第一题有些情况没考虑到，于是最后A题这个大水题很遗憾地没过。

一开始师父有事就跑了，大概1个多小时以后又回来了。

这短时间LCC沉浸在G中，我沉浸在J中，貌似都不可自拔

然后后来我觉得J太大自然了，于是又看了一个Board，UESTC的队过了I，然后赶去围观，果断发现是水题，于是切掉。

接下来LCC大神在G题题意极度不清晰的情况下暴力试出了Accepted，Orz。

然后后来又看到了UESTC那队把B过了，我一看，迅速反应出这和昨天那题最大流的构图是一样，只要求个费用流就可以了。

但是第一遍提交的时候出现的很神奇的事情，我交上去Waiting，然后等了N久之后，UESTC也交了一个Waiting，在之后，LCC也交了一个Waiting，我顿时惊叹，题库爆了！然后再过了几秒之后，3个TLE出现，顿时觉得有点假。。。

然后手测了一些数据，发现由于精度问题，费用流跑了正向边以后又去跑反向边去了，然后+个eps以后就Y了。

此期间LCC用小号对E题不断进行轰炸，后来发现是输出的时候格式出了问题…

师父一跑来就说，D是数论，我来切，然后就切掉了~Orz！！！！

接着我看了A题，觉得比较简单，于是开切，然后由于一种情况没有考虑到，应该说题意上有一点误解。

就是这一句

the travel covered by a ticket be completed in order and without intervening travel

然后在我脑海里形成映像，后面的路程也是要完全吻合的，于是悲剧。。。

最后就5题了(B D E G I)，师父表示当年WF2006最多的一队也就是6题。我顿时捶胸顿足……就差了我的A题啊

都是我的错……

下面简单说说我做的两题（都超级水）：

B题就是要填一个m*n的矩阵c，分别给出每一行和每一列的和，然后每个格子还有一个实数权w，最后输出最小和最大的

Sum{c[i][j]*w[i][j]}，有一些实权位-1的表示不可填。然后就是最小费用最大流+最大费用最大流了。

http://acm.hust.edu.cn:8080/judge/contest/viewProblem.action?pid=22056

代码：http://xiudaima.appspot.com/code/detail/4554012

I题就一个Floyd

然后现在把A题补一下。

【题目链接】http://acm.hust.edu.cn:8080/judge/contest/viewProblem.action?pid=22055

就是给定20张机票，每张机票有一条旅行路线和一个价格，每次可以用一张机票路线的前缀，然后给定20个询问，每个询问都是一条路线，问你通过这些机票，最少花多少钱可以完成这条路线。完成这条路线时必须按顺序经过路线上的点，但是在路线的各点中间，你可以先跑去其它地方再飞回来。

【解法】

F[i,j,k]表示已经完成这个路线的前i个点，现在在第j张飞机票的第k个点时，最少的费用是多少。

由于有后效性，用SPFA来转移之。

然后就解决了

【Hint】题目给出的各城市的编号是任意的。。。如果处理的不好要先离散化。一般直接判等于就行。

【CODE】

http://xiudaima.appspot.com/code/detail/4490007

最后Orz LCC、Orz AC，鄙视我自己