CTSC2011《幸福路径》解题报告
ltl 2011-5-26软件综合
AC(Accepted,即满分的意思)这道题目是我这次CTSC2011(国际信息奥赛中国国家队选拔赛暨精英赛)拿金牌的主要原因,在此写一份解题报告作为纪念,同时也和大家分享一下。

题目简述:
n点m边带点权有向图,起点处体力为1,每走过一边体力乘p(0<p<1),路径幸福指数为各点点权*体力之和,路径可以无限长,求最大幸福指数。
n≤100,m≤1000。要求1s内出解。

算法描述:
最暴力的方式是用Bellman-Ford迭代,也就是每次从所有点往下走一步,不断迭代直到数值小于一个极小值,对答案没有什么影响的时候结束,但是p>=0.999的时候会TLE(超时),而且这不是精确算法。
对于一个固定的环,可以知道如果在里面无限绕圈,结果为一等比数列求和求极限,且推出的式子包含环上绕一圈的收益和环的长度两个参数,所以只要枚举环的长度和起点,求出在此条件下收益最大的环即可。而由于对于每一个点,下一步的最优决策其实是固定的,所以路径必定为走一条链,然后停下或者进入一个环开始死循环,所以只要枚举一条路径,再枚举一个环即可。
为了解决以上问题,可以用DP(动态规划),f[i,j,k]表示从j到k走i步的收益最大路径,则f[i,j,j]就是一个环,可以很方便地解决以上问题,时间复杂度为O(n^2*m)。
至于这个DP怎么做,其实很简单,f[i,j,k]=Sigma{f[i-1,j,l]+w[k]*p^i},其中l为满足存在l->k这条边的点,w为点权。

总结:
这题刚开始想到的是二分答案的思路,进过尝试后发现完全无法通过数学变换得到判定性问题的图论解,由尝试了矩阵快速幂,但是同时存在常数矩阵和系数矩阵的时候按照普通的方式进行矩阵快速幂会使矩阵内的元素变成多项式的形式,虽然解题报告中也有这种方式,但是还是不理解如何做到了,且此方法只能得到近似解。于是开始分析问题的特性,得到了路径形态的猜想,并进行了不是很严格的证明,得到了一个优秀的DP算法。

我的程序(C++):

#include &lt;iostream&gt;
#include &lt;cmath&gt;
#include &lt;cstdio&gt;
#include &lt;cstdlib&gt;
#include &lt;memory.h&gt;
#include &lt;cstring&gt;
#include &lt;algorithm&gt;
#include &lt;iomanip&gt;

#define Max(a, b)            (a &gt; b ? a : b)

using namespace std;

const int MaxN = 110, MaxM = 1100;

int n, m, S, u[MaxM], v[MaxM];
double p, a[MaxN], f[MaxN][MaxN][MaxN], g[MaxN], Power[MaxN], Ans;

void Init()
{
    scanf(&quot;%d%d&quot;, &amp;n, &amp;m);
    for (int i = 1; i &lt;= n; ++i)
        scanf(&quot;%lf&quot;,&amp;a[i]);
    scanf(&quot;%d%lf&quot;, &amp;S, &amp;p);
    for (int i = 1; i &lt;= m; ++i)
        scanf(&quot;%d%d&quot;, &amp;u[i], &amp;v[i]);
    Power[0] = 1;
    for (int i = 1; i &lt;= n; ++i)
        Power[i] = Power[i-1]*p;
}

int main()
{
    freopen(&quot;path.in&quot;, &quot;r&quot;, stdin);
    freopen(&quot;path.out&quot;, &quot;w&quot;, stdout);
    Init();
    for (int i = 0, j, k; i &lt;= n; ++i)
        for (j = 1; j &lt;= n; ++j)
            for (k = 1; k &lt;= n; ++k)
                f[i][j][k] = -1E20;
    for (int i = 1; i &lt;= n; ++i)
        g[i] = f[0][i][i] = a[i];
    for (int i = 1, j, k; i &lt;= n; ++i)
        for (j = 1; j &lt;= n; ++j)
            for (k = 1; k &lt;= m; ++k)
                f[i][j][v[k]] = Max(f[i][j][v[k]], f[i-1][j][u[k]]+a[v[k]]*Power[i]);
    for (int i = 1, j; i &lt;= n; ++i)
        for (j = i; j &lt;= n; ++j)
            g[i] = Max(g[i], (f[j][i][i]-a[i]*Power[j])/(1-Power[j]));
    for (int i = 1, j; i &lt;= n; ++i)
        for (j = 0; j &lt;= n; ++j)
            Ans = Max(Ans, f[j][S][i]-a[i]*Power[j]+Power[j]*g[i]);
    cout &lt;&lt; setprecision(1) &lt;&lt; fixed &lt;&lt; Ans &lt;&lt; endl;
    return 0;
}



代码不长,主要还是在思维复杂度上,赛场上我用了两个小时来完成本题。
如果有什么不足,还请大家指出。  
+1500  科创币    科创论坛   2011-05-26   详细阐述了思路。
来自 软件综合
 
2011-5-26 09:09:02
ltl(作者)
1楼
谁教我一下怎么弄代码高亮,或者请会的管理员直接帮我修改一下,谢谢
折叠评论
加载评论中,请稍候...
折叠评论
ltl(作者)
2楼
表示编程版好冷清啊……
折叠评论
加载评论中,请稍候...
折叠评论
3楼
初三的OIer表示完全没懂
我不会背包不会DFS只会乱弄,混了个普及组一等
现在表示压力巨大
折叠评论
1
加载评论中,请稍候...
折叠评论
ltl(作者)
4楼
我现在压力也巨大……我觉得我NOI会悲剧……
折叠评论
加载评论中,请稍候...
折叠评论
5楼
ls大神牛,别这么说
我觉得我noip会杯具
拿到题目,知道是01背包,就是不会写
你说我怎么参加提高组
折叠评论
加载评论中,请稍候...
折叠评论
ltl(作者)
6楼
我NOIP2010已经悲剧了,比省一线低10分……n和m敲错少了90分……还好高一拿过了……

01背包………………

for (int i = 1; i <= n; ++i)
    for (int j = V; j >= a[ i ]; --j)
        f[j] = Max(f[j], f[j-a[ i ]]+w[i]);

srO………………Orz
折叠评论
加载评论中,请稍候...
折叠评论
ltl(作者)
7楼
为什么每个a后面的 [ i ]都消失了……
折叠评论
加载评论中,请稍候...
折叠评论
ltl(作者)
8楼
终于正常了……居然[ i ]是斜体符号……
折叠评论
加载评论中,请稍候...
折叠评论
9楼
楼主已得道成仙,鄙BASIC菜甘拜下风。编程算法之天才,自古奇缺。
折叠评论
加载评论中,请稍候...
折叠评论
2011-5-27 07:50:44
ltl(作者)
10楼
我已经被各种虐爆了……亚太奥赛只剩Silver了……双Gold失败………………

话说国家集训队第一成绩比我高了50%以上了…………
折叠评论
加载评论中,请稍候...
折叠评论
11楼
至今只会pascal的表示看不懂c++
折叠评论
加载评论中,请稍候...
折叠评论
ltl(作者)
12楼
好吧……

for i:=1 to n do
    for j:=V downto a[i] do
        f[j]:=Max(f[j], f[j-a[i]]+w[i]);

双语言选手继续飘过……
折叠评论
加载评论中,请稍候...
折叠评论
2011-5-28 17:54:52
2011-5-28 17:54:52
13楼
[quote]引用第12楼ltl于2011-05-27 10:03发表的  :
好吧……
[code]
for i:=1 to n do
    for j:=V downto a[i] do
        f[j]:=Max(f[j], f[j-a[i]]+w[i]);
.......
[/quote]

楼主已CP通吃,将来必有一番作为,至少也能当个OI辅导。
折叠评论
加载评论中,请稍候...
折叠评论
2011-5-29 16:06:32
ltl(作者)
14楼
CP通吃的我们学校遍地都是……

这个……OI辅导这种事情貌似都是叫保送Tsinghua的吧……而且一般是要有国家队或者至少国家集训队的吧……
折叠评论
加载评论中,请稍候...
折叠评论
2011-5-31 19:42:15
2011-5-31 19:42:15
15楼
惊见神牛OIer..
[s:261] 膜拜下。
还有今天刚ac首道Trie的题[s:182]
折叠评论
加载评论中,请稍候...
折叠评论
2011-6-1 16:24:54
ltl(作者)
16楼
呃,关于Trie以及AC自动机的题目我可能在接下来一段时间有空的时候会写一份解题报告发上来的。
折叠评论
加载评论中,请稍候...
折叠评论
ltl(作者)
17楼
顺便说一下……我不是神牛………………我巨弱………………我这种连APIO都没金的人怎么可能是神牛…………

膜拜我不如膜拜国家队的fhq吧,人家CTSC两试都是Rank1,还是虐爆Rank2的那种………………而且比我小………………
折叠评论
加载评论中,请稍候...
折叠评论
18楼
很关心这些OIer最后出路如何,貌似很多都脱离计算机行业了
折叠评论
加载评论中,请稍候...
折叠评论
ltl(作者)
19楼
不会啊,对于我们学校的,成功的(NOI现场点招)的最后大学很多都搞ACM,工作一般还是选软件公司吧
折叠评论
加载评论中,请稍候...
折叠评论
ltl(作者)
20楼
至于个别像cqx那样的神犇去了pku哲学系嘛……这个不解释……
折叠评论
加载评论中,请稍候...
折叠评论
ltl(作者)
21楼
引用第13楼novakon于2011-05-28 17:54发表的  :


楼主已CP通吃,将来必有一番作为,至少也能当个OI辅导。

其实我突然想起来我们这还有CPJ通吃的………………好好的题目脑残写什么Java………………(虽然我有点时候也写BrainF**k……)
折叠评论
加载评论中,请稍候...
折叠评论
2011-8-18 23:10:40
2011-8-18 23:10:40
22楼
APIO被虐爆的傻×首先Orz楼主……只能等待NOIP2011的最后机会了……
折叠评论
加载评论中,请稍候...
折叠评论
2011-9-7 09:54:07
2011-9-7 09:54:07
ltl(作者)
23楼
555……OI生涯完挂……
折叠评论
加载评论中,请稍候...
折叠评论

想参与大家的讨论?现在就 登录 或者 注册

插入资源
全部
图片
视频
音频
附件
全部
未使用
已使用
正在上传
空空如也~
上传中..{{f.progress}}%
处理中..
上传失败,点击重试
{{f.name}}
空空如也~
(视频){{r.oname}}
{{selectedResourcesId.indexOf(r.rid) + 1}}
ID:{{user.uid}}
{{user.username}}
{{user.info.certsName}}
{{user.description}}
{{format("YYYY/MM/DD", user.toc)}}注册,{{fromNow(user.tlv)}}活动
{{submitted?"":"投诉"}}
请选择违规类型:
{{reason.description}}
支持的图片格式:jpg, jpeg, png