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 <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("XXXXXXXX", "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   详细阐述了思路。
来自:计算机科学 / 软件综合
 
ltl 作者
10年3个月前
1楼
谁教我一下怎么弄代码高亮,或者请会的管理员直接帮我修改一下,谢谢
回复
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltl作者
10年3个月前
2楼
表示编程版好冷清啊……
回复
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltc
10年3个月前
3楼
初三的OIer表示完全没懂
我不会背包不会DFS只会乱弄,混了个普及组一等
现在表示压力巨大
回复
评论
1
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltl作者
10年3个月前
4楼
我现在压力也巨大……我觉得我NOI会悲剧……
回复
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltc
10年3个月前
5楼
ls大神牛,别这么说
我觉得我noip会杯具
拿到题目,知道是01背包,就是不会写
你说我怎么参加提高组
回复
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltl作者
10年3个月前
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
回复
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltl作者
10年3个月前
7楼
为什么每个a后面的 [ i ]都消失了……
回复
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltl作者
10年3个月前
8楼
终于正常了……居然[ i ]是斜体符号……
回复
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
novakon
10年3个月前
9楼
楼主已得道成仙,鄙BASIC菜甘拜下风。编程算法之天才,自古奇缺。
回复
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltl作者
10年3个月前
10楼
我已经被各种虐爆了……亚太奥赛只剩Silver了……双Gold失败………………

话说国家集训队第一成绩比我高了50%以上了…………
回复
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltc
10年3个月前
11楼
至今只会pascal的表示看不懂c++
回复
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltl作者
10年3个月前
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]);

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

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

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


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

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

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

所属专业
上级专业
同级专业
ltl
学者 笔友
文章
50
回复
3644
学术分
2
2009/09/27注册,2 年前活动
暂无简介
%7B%22isDisplay%22%3Atrue%7D

仅供内部学术交流或培训使用,请先保存到本地。本内容不代表科创观点,未经原作者同意,请勿转载。

插入资源
全部
图片
视频
音频
附件
全部
未使用
已使用
正在上传
空空如也~
上传中..{{f.progress}}%
处理中..
上传失败,点击重试
等待中...
{{f.name}}
空空如也~
(视频){{r.oname}}
{{selectedResourcesId.indexOf(r.rid) + 1}}
处理中..
处理失败
插入表情
我的表情
共享表情
Emoji
上传
注意事项
最大尺寸100px,超过会被压缩。为保证效果,建议上传前自行处理。
建议上传自己DIY的表情,严禁上传侵权内容。
点击重试等待上传{{s.progress}}%处理中...已上传
空空如也~
草稿箱
加载中...
此处只插入正文,如果要使用草稿中的其余内容,请点击继续创作。
{{fromNow(d.toc)}}
{{getDraftInfo(d)}}
标题:{{d.t}}
内容:{{d.c}}
继续创作
删除插入插入
{{forum.displayName}}
{{forum.countThreads}}
篇文章,
{{forum.countPosts}}
条回复
{{forum.description || "暂无简介"}}
ID: {{user.uid}}
学术分隐藏
{{submitted?"":"投诉或举报"}}
请选择违规类型:
{{reason.description}}
支持的图片格式:jpg, jpeg, png
插入公式
分享回复:{{shareId}}
加载中...
评论控制
加载中...
文号:{{pid}}
加载中...
详情
详情
推送到专栏从专栏移除
设为匿名取消匿名
查看作者
回复
只看作者
加入收藏取消收藏
加入关注取消关注
折叠回复
置顶取消置顶
评学术分
鼓励
设为精选取消精选
建议修改
编辑
通过审核
评论控制
退修或删除
历史版本
违规记录
投诉或举报
加入黑名单移除黑名单
查看IP
{{format('YYYY/MM/DD HH:mm:ss', toc)}}
下载资料
{{fileName}}
大小:{{size}}
下载当前附件将花费 {{costMessage}}
{{description}}
你当前剩余 {{holdMessage}}
{{fileName}}
大小:{{size}}
当前附件免费。
你已购买过此附件,下载当前附件不需要花费积分。
加载中...
{{errorInfo}}
附件已丢失
当前账号的附件下载数量限制如下:
时段 个数
{{f.startingTime}}点 - {{f.endTime}}点 {{f.fileCount}}