首页 > 代码库 > BZOJ 1415 【NOI2005】 聪聪和可可
BZOJ 1415 【NOI2005】 聪聪和可可
题目链接:聪聪和可可
一道水题……开始还看错题了,以为边带权……强行\( O(n^3)\)预处理……
首先,我们显然可以预处理出一个数组\( p[u][v] \)表示可可在点\(u\),聪聪在点\(v\)的时候聪聪下一步会往哪里走。然后……一个记忆化搜索就轻易地解决掉了……
至于转移方程吗,我觉得也没有必要写了……你要是实在不知道就看一看代码吧……
下面贴代码:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) #define N 1010 using namespace std; typedef double llg; int n,E,C,M,dis[N],p[N][N],fr[N],d[N],ld; int head[N],next[N<<1],to[N<<1],tt,du[N]; llg f[N][N]; bool vis[N],w[N][N]; void solve(int S){ for(int i=1;i<=n;i++) dis[i]=vis[i]=0; vis[S]=1; d[ld=1]=S; du[S]++; for(int l=1,u;u=d[l],l<=ld;l++) for(int i=head[u],v;v=to[i],i;i=next[i]) if(!vis[v]) dis[v]=dis[u]+1,vis[v]=1,d[++ld]=v,fr[v]=u; else if(dis[v]==dis[u]+1) fr[v]=min(fr[v],u); for(int i=1;i<=n;i++) p[S][i]=fr[i]; } llg search(int u,int v){ if(w[u][v]) return f[u][v]; if(p[u][v]==u || p[u][p[u][v]]==u) return 1; w[u][v]=1; for(int i=head[u];i;i=next[i]) f[u][v]+=search(to[i],p[u][p[u][v]])+1; f[u][v]+=search(u,p[u][p[u][v]])+1; return f[u][v]/=(llg)du[u]; } int main(){ File("a"); scanf("%d %d %d %d",&n,&E,&C,&M); for(int i=1,x,y;i<=E;i++){ scanf("%d %d",&x,&y); du[x]++; du[y]++; to[++tt]=y;next[tt]=head[x];head[x]=tt; to[++tt]=x;next[tt]=head[y];head[y]=tt; } for(int i=1;i<=n;i++) solve(i),w[i][i]=1; printf("%.3lf",search(M,C)); return 0; }
BZOJ 1415 【NOI2005】 聪聪和可可
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。