CTSC2011《幸福路径》解题报告
ltl2011/05/26软件综合 IP:福建
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 <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <memory.h>
#include <cstring>
#include <algorithm>
#include <iomanip>

#define Max(a, b)            (a > 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("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%lf",&a[i]);
    scanf("%d%lf", &S, &p);
    for (int i = 1; i <= m; ++i)
        scanf("%d%d", &u[i], &v[i]);
    Power[0] = 1;
    for (int i = 1; i <= n; ++i)
        Power[i] = Power[i-1]*p;
}

int main()
{
    freopen("XXXXXXX", "r", stdin);
    freopen("path.out", "w", stdout);
    Init();
    for (int i = 0, j, k; i <= n; ++i)
        for (j = 1; j <= n; ++j)
            for (k = 1; k <= n; ++k)
                f[i][j][k] = -1E20;
    for (int i = 1; i <= n; ++i)
        g[i] = f[0][i][i] = a[i];
    for (int i = 1, j, k; i <= n; ++i)
        for (j = 1; j <= n; ++j)
            for (k = 1; k <= 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 <= n; ++i)
        for (j = i; j <= n; ++j)
            g[i] = Max(g[i], (f[j][i][i]-a[i]*Power[j])/(1-Power[j]));
    for (int i = 1, j; i <= n; ++i)
        for (j = 0; j <= n; ++j)
            Ans = Max(Ans, f[j][S][i]-a[i]*Power[j]+Power[j]*g[i]);
    cout << setprecision(1) << fixed << Ans << endl;
    return 0;
}



代码不长,主要还是在思维复杂度上,赛场上我用了两个小时来完成本题。
如果有什么不足,还请大家指出。  
+1500  科创币    科创网    2011/05/26 详细阐述了思路。
来自:计算机科学 / 软件综合
24
 
已屏蔽 原因:{{ notice.reason }}已屏蔽
{{notice.noticeContent}}
~~空空如也
ltl 作者
13年0个月前 IP:未同步
296713
谁教我一下怎么弄代码高亮,或者请会的管理员直接帮我修改一下,谢谢
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltl作者
13年0个月前 IP:未同步
296746
表示编程版好冷清啊……
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltc
13年0个月前 IP:未同步
296754
初三的OIer表示完全没懂
我不会背包不会DFS只会乱弄,混了个普及组一等
现在表示压力巨大
引用
评论
1
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltl作者
13年0个月前 IP:未同步
296766
我现在压力也巨大……我觉得我NOI会悲剧……
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltc
13年0个月前 IP:未同步
296772
ls大神牛,别这么说
我觉得我noip会杯具
拿到题目,知道是01背包,就是不会写
你说我怎么参加提高组
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltl作者
13年0个月前 IP:未同步
296773
我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
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltl作者
13年0个月前 IP:未同步
296774
为什么每个a后面的 [ i ]都消失了……
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltl作者
13年0个月前 IP:未同步
296776
终于正常了……居然[ i ]是斜体符号……
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
novakon
13年0个月前 IP:未同步
296811
楼主已得道成仙,鄙BASIC菜甘拜下风。编程算法之天才,自古奇缺。
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltl作者
13年0个月前 IP:未同步
296826
我已经被各种虐爆了……亚太奥赛只剩Silver了……双Gold失败………………

话说国家集训队第一成绩比我高了50%以上了…………
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltc
13年0个月前 IP:未同步
296832
至今只会pascal的表示看不懂c++
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltl作者
13年0个月前 IP:未同步
296834
好吧……

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

双语言选手继续飘过……
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
novakon
12年11个月前 IP:未同步
297058
[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辅导。
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltl作者
12年11个月前 IP:未同步
297214
CP通吃的我们学校遍地都是……

这个……OI辅导这种事情貌似都是叫保送Tsinghua的吧……而且一般是要有国家队或者至少国家集训队的吧……
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
caoyuan9642
12年11个月前 IP:未同步
297510
惊见神牛OIer..
[s:261] 膜拜下。
还有今天刚ac首道Trie的题[s:182]
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltl作者
12年11个月前 IP:未同步
297621
呃,关于Trie以及AC自动机的题目我可能在接下来一段时间有空的时候会写一份解题报告发上来的。
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltl作者
12年11个月前 IP:未同步
297622
顺便说一下……我不是神牛………………我巨弱………………我这种连APIO都没金的人怎么可能是神牛…………

膜拜我不如膜拜国家队的fhq吧,人家CTSC两试都是Rank1,还是虐爆Rank2的那种………………而且比我小………………
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
warmonkey
12年11个月前 IP:未同步
297625
很关心这些OIer最后出路如何,貌似很多都脱离计算机行业了
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltl作者
12年11个月前 IP:未同步
297632
不会啊,对于我们学校的,成功的(NOI现场点招)的最后大学很多都搞ACM,工作一般还是选软件公司吧
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltl作者
12年11个月前 IP:未同步
297673
至于个别像cqx那样的神犇去了pku哲学系嘛……这个不解释……
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltl作者
12年11个月前 IP:未同步
297675
引用第13楼novakon于2011-05-28 17:54发表的  :


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

其实我突然想起来我们这还有CPJ通吃的………………好好的题目脑残写什么Java………………(虽然我有点时候也写BrainF**k……)
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
百死不悔
12年9个月前 IP:未同步
316965
APIO被虐爆的傻×首先Orz楼主……只能等待NOIP2011的最后机会了……
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltl作者
12年8个月前 IP:未同步
320505
555……OI生涯完挂……
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论

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

所属专业
上级专业
同级专业
ltl
学者 笔友
文章
50
回复
3650
学术分
2
2009/09/27注册,1个月9天前活动
暂无简介
主体类型:个人
所属领域:无
认证方式:邮箱
IP归属地:未同步
文件下载
加载中...
{{errorInfo}}
{{downloadWarning}}
你在 {{downloadTime}} 下载过当前文件。
文件名称:{{resource.defaultFile.name}}
下载次数:{{resource.hits}}
上传用户:{{uploader.username}}
所需积分:{{costScores}},{{holdScores}}下载当前附件免费{{description}}
积分不足,去充值
文件已丢失

当前账号的附件下载数量限制如下:
时段 个数
{{f.startingTime}}点 - {{f.endTime}}点 {{f.fileCount}}
视频暂不能访问,请登录试试
仅供内部学术交流或培训使用,请先保存到本地。本内容不代表科创观点,未经原作者同意,请勿转载。
音频暂不能访问,请登录试试
支持的图片格式:jpg, jpeg, png
插入公式
评论控制
加载中...
文号:{{pid}}
投诉或举报
加载中...
{{tip}}
请选择违规类型:
{{reason.type}}

空空如也

加载中...
详情
详情
推送到专栏从专栏移除
设为匿名取消匿名
查看作者
回复
只看作者
加入收藏取消收藏
折叠回复
置顶取消置顶
评学术分
鼓励
设为精选取消精选
管理提醒
编辑
通过审核
评论控制
退修或删除
历史版本
违规记录
投诉或举报
加入黑名单移除黑名单
查看IP
{{format('YYYY/MM/DD HH:mm:ss', toc)}}