题解

16 条题解

  • 0
    @ 2016-03-18 07:49:23

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<queue>

    using namespace std;

    const int maxn = 1009;

    double dp[maxn][maxn];
    int d[maxn][maxn], deg[maxn], s[maxn][maxn], N, S, T;
    bool inq[maxn], vis[maxn][maxn];
    queue<int> q;

    struct edge {
    int to;
    edge* next;
    } E[maxn << 1], *pt = E, *head[maxn];

    void AddEdge(int u, int v) {
    deg[pt->to = v]++;
    pt->next = head[u];
    head[u] = pt++;
    }

    void Spfa(int d[], int S) {
    for(int i = 0; i < N; i++)
    d[i] = maxn, inq[i] = false;
    d[S] = 0; inq[S] = true;
    q.push(S);
    while(!q.empty()) {
    int x = q.front(); q.pop();
    for(edge* e = head[x]; e; e = e->next) if(d[e->to] > d[x] + 1) {
    d[e->to] = d[x] + 1;
    if(!inq[e->to])
    q.push(e->to), inq[e->to] = true;
    }
    }
    }

    void Init() {

    int m;
    scanf("%d%d%d%d", &N, &m, &S, &T); S--; T--;
    memset(deg, 0, sizeof(int) * N);
    while(m--) {
    int u, v;
    scanf("%d%d", &u, &v); u--; v--;
    AddEdge(u, v);
    AddEdge(v, u);
    }

    for(int i = 0; i < N; i++) Spfa(d[i], i);

    memset(s, -1, sizeof s);

    for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++)
    for(edge* e = head[i]; e; e = e->next)if(d[i][j] == d[e->to][j] + 1) {
    if(~s[i][j])
    s[i][j] = min(s[i][j], e->to);
    else
    s[i][j] = e->to;
    }

    memset(vis, 0, sizeof vis);
    for(int i = 0; i < N; i++) {
    dp[i][i] = 0;
    vis[i][i] = true;
    for(int j = 0; j < N; j++)
    if(i != j && ~s[i][j] && (s[i][j] == j || s[s[i][j]][j] ==j)) {
    dp[i][j] = 1;
    vis[i][j] = true;
    }
    }

    }

    double Dp(int x, int y) {
    if(vis[x][y]) return dp[x][y];
    vis[x][y] = true;

    dp[x][y] = Dp(s[s[x][y]][y],y);
    for(edge* e = head[y]; e; e = e->next)
    dp[x][y] += Dp(s[s[x][y]][y],e->to);

    return ++(dp[x][y] /= deg[y] + 1);
    }

    int main() {

    Init();
    printf("%.3lf\n", Dp(S, T));

    return 0;
    }

  • 0
    @ 2014-07-19 17:04:22

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 21016 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 21020 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 21016 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 21016 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 21020 KiB, score = 10
    测试数据 #5: Accepted, time = 46 ms, mem = 21020 KiB, score = 10
    测试数据 #6: Accepted, time = 46 ms, mem = 21020 KiB, score = 10
    测试数据 #7: Accepted, time = 15 ms, mem = 21020 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 21016 KiB, score = 10
    测试数据 #9: Accepted, time = 46 ms, mem = 21020 KiB, score = 10
    Accepted, time = 183 ms, mem = 21020 KiB, score = 100
    用dp[s,t]表示聪聪在s,可可在t时聪聪吃到可可的期望。
    dp方程程序里有。
    其中p[s,t]表示聪聪在s点,可可在t点,聪聪走一步会走到哪里,自然p[p[s,t],t]就是聪聪走两步会走到哪里。p数组可以用SPFA预处理出来。

    Block Code

    #include <cstdio>
    #include <cstring>
    #define N 1005
    #define M N*N

    int h[N], nxt[M], to[M], cnt = 0;
    int dis[N], p[N][N];
    double dp[N][N];
    bool v[N][N], vis[N];
    int q[3*N], f, r;
    int n, s, t;

    void add(int u, int v) {
    nxt[cnt] = h[u];
    to[cnt] = v;
    h[u] = cnt++;
    }

    void bfs(int s) {
    memset(dis,127,sizeof(dis));
    f = r = 0;
    q[r++] = s;
    dis[s] = 0;
    p[s][s] = s;
    vis[s] = 1;
    while(f < r) {
    int u = q[f++];
    vis[u] = 0;
    for(int i=h[u];i!=-1;i=nxt[i]) {
    int v = to[i];
    if(!vis[v] && dis[v]>dis[u]+1) {
    dis[v]=dis[u]+1;
    p[v][s] = u;
    q[r++] = v;
    vis[v] = 1;
    } else if(dis[v]==dis[u]+1 && u<p[v][s]) {
    p[v][s] = u;
    }
    }
    }
    }

    double calc(int s, int t) {
    if(s == t) return 0;
    if(v[s][t]) return dp[s][t];
    v[s][t] = 1;
    if(p[s][t]==t || p[p[s][t]][t]==t) return dp[s][t] = 1;
    dp[s][t] += calc(p[p[s][t]][t], t);
    int k = 1;
    for(int i=h[t];i!=-1;i=nxt[i]) {
    dp[s][t] += calc(p[p[s][t]][t], to[i]);
    k++;
    }
    return dp[s][t] = dp[s][t] / k + 1;
    }

    int main() {
    freopen("cchkk.in","r",stdin);
    freopen("cchkk.out","w",stdout);

    int x, y, m;
    memset(h,-1,sizeof(h));
    memset(vis,0,sizeof(vis));

    scanf("%d%d%d%d", &n, &m, &s, &t);
    while(m--) {
    scanf("%d%d", &x, &y);
    add(x,y); add(y,x);
    }
    for(x = 1; x <= n; x++)
    for(y = 1; y <= n; y++) {
    dp[x][y] = 0.0;
    v[x][y] = 0;
    }
    for(m = 1; m <= n; m++)
    bfs(m);
    printf("%.3lf", calc(s, t));

    fclose(stdin); fclose(stdout);
    return 0;
    }

  • 0
    @ 2014-03-03 14:31:34

    spfa预处理+DP
    编译成功

    测试数据 #0: Accepted, time = 7 ms, mem = 13256 KiB, score = 10
    测试数据 #1: Accepted, time = 7 ms, mem = 13256 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 13256 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 13260 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 13256 KiB, score = 10
    测试数据 #5: Accepted, time = 109 ms, mem = 13268 KiB, score = 10
    测试数据 #6: Accepted, time = 140 ms, mem = 13268 KiB, score = 10
    测试数据 #7: Accepted, time = 46 ms, mem = 13256 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 13256 KiB, score = 10
    测试数据 #9: Accepted, time = 78 ms, mem = 13280 KiB, score = 10
    Accepted, time = 447 ms, mem = 13280 KiB, score = 100

    代码:
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <deque>
    #include <vector>

    using namespace std ;

    #define AddEdge( s , t ) e[ s ].pb( t ) , e[ t ].pb( s )
    #define maxn 1010
    #define pb push_back
    #define pf push_front
    #define inf 0x7fffffff
    #define travel( s ) for ( vector < int > :: iterator p = e[ s ].begin( ) ; p != e[ s ].end( ) ; ++ p )
    #define rep( i , x ) for ( int i = 0 ; i ++ < x ; )

    vector < int > e[ maxn ] ;
    int n , m , st , to , next[ maxn ][ maxn ] , d[ maxn ] ;

    int dist[ maxn ] ;
    deque < int > q ;
    bool f[ maxn ] ;

    void spfa( int S ) {
    memset( f , false , sizeof( f ) ) , q.clear( ) ;
    rep( i , n ) dist[ i ] = inf ;
    dist[ S ] = 0 , f[ S ] = true , q.pf( S ) ;
    while ( ! q.empty( ) ) {
    int v = q.front( ) ; q.pop_front( ) , f[ v ] = false ;
    travel( v ) if ( dist[ *p ] > dist[ v ] + 1 ) {
    dist[ *p ] = dist[ v ] + 1 ;
    if ( ! f[ *p ] ) {
    f[ *p ] = true ;
    if ( ! q.empty( ) && dist[ *p ] < dist[ q.front( ) ] ) q.pf( *p ) ; else q.pb( *p ) ;
    }
    }
    }
    }

    double dp[ maxn ][ maxn ] ;
    bool flag[ maxn ][ maxn ] ;

    double Dp( int v , int u ) {
    if ( flag[ v ][ u ] ) return dp[ v ][ u ] ;
    if ( v == u ) {
    dp[ v ][ u ] = 0 , flag[ v ][ u ] = true ;
    return dp[ v ][ u ] ;
    }
    int k = next[ v ][ u ] ;
    if ( k != u ) k = next[ k ][ u ] ;
    dp[ v ][ u ] = 1 ;
    if ( k != u ) {
    travel( u ) dp[ v ][ u ] += Dp( k , *p ) / double( d[ u ] + 1 ) ;
    dp[ v ][ u ] += Dp( k , u ) / double( d[ u ] + 1 ) ;
    }
    flag[ v ][ u ] = true ;
    return dp[ v ][ u ] ;
    }

    int main( ) {
    scanf( "%d%d" , &n , &m ) ;
    scanf( "%d%d" , &st , &to ) ;
    memset( d , 0 , sizeof( d ) ) ;
    while ( m -- ) {
    int s , t ; scanf( "%d%d" , &s , &t ) ; AddEdge( s , t ) ;
    ++ d[ s ] , ++ d[ t ] ;
    }
    memset( next , 0 , sizeof( next ) ) ;
    rep( i , n ) {
    spfa( i ) ;
    rep( j , n ) travel( j ) if ( ! next[ j ][ i ] || dist[ *p ] < dist[ next[ j ][ i ] ] || ( dist[ *p ] == dist[ next[ j ][ i ] ] && *p < next[ j ][ i ] ) ) {
    next[ j ][ i ] = *p ;
    }
    }
    memset( flag , false , sizeof( flag ) ) ;
    printf( "%.3f\n" , Dp( st , to ) ) ;
    return 0 ;
    }

  • 0
    @ 2012-07-26 16:52:05

    WA了一次

    提醒一下,聪聪是每回合分别做两次走一步决策,而不是做走两步的决策。

  • 0
    @ 2009-10-25 20:41:24

    楼下神牛bsNOI的题,orz!!!!!!!!!

  • 0
    @ 2009-10-25 18:36:28

    noip难度的noi题

  • 0
    @ 2009-10-25 18:25:35

    ms题意不太清楚

  • 0
    @ 2009-10-25 11:29:02

    哈哈哈哈哈哈

  • 0
    @ 2009-10-25 08:21:04

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2009-10-24 20:36:51

    so difficult! - -||

  • 0
    @ 2010-03-01 22:20:01

    。。第二十个

    交了N次

    通过率50%-->36%

    第一个难度4的题

    庆祝下

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2009-10-24 18:44:21

    图论+DP

    注意聪聪一次最多可以走两步!

  • 0
    @ 2009-10-24 18:39:39

    平均!!

  • 0
    @ 2009-10-25 10:45:15

    AC

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 88ms

    ├ 测试数据 07:答案正确... 72ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 72ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:232ms

    sunny果然不错,conan最强……

  • 0
    @ 2009-10-24 18:11:10

    我不会哦

  • 1

信息

ID
1675
难度
5
分类
动态规划 | 树形DP概率论 点击显示
标签
递交数
345
已通过
115
通过率
33%
被复制
1
上传者