uva-10828 期望dp+gauss

浅浅的花香味﹌ 2022-05-09 11:08 136阅读 0赞

[传送门][Link 1]

题意：给你一个有向图，从1号节点出发，问经过某个点的期望次数。

思路：传递闭包写错wa到哭。设 dp\[i\]为经过i点期望

dp\[v\]=dp\[u1\]\*p1+dp\[u2\]\*p2+....（对于第一个点应该再+1）

将每个dp看做变量，就可以构成n\*n的矩阵比如样例1构成矩阵如下

\-1    1  0    -1

0.5   -1   0   0

0    0.5  -1  0

用高斯消元解就可以，对于有解得dp直接输出就可以，对于无穷的，与他相关的点也无穷，也就是他传递闭包能到的点。

代码一：

#include<bits/stdc++.h>
    using namespace std;
    #define eps 1e-9
    const int MAXN=110;
    double a[MAXN][MAXN], x[MAXN];
    int equ, var;
    int n;
    
    int gauss(){
        int i, j, k, col, max_r;
        for(k=0, col=0; k<equ&&col<var; k++, col++){
            max_r=k;
            for(i=k+1; i<equ; i++)
                if(fabs(a[i][col])>fabs(a[max_r][col]))
                    max_r=i;
    
            if(fabs(a[max_r][col])<eps) return 0;
            if(k!=max_r){
                for(j=col; j<var; j++)
                    swap(a[k][j], a[max_r][j]);
                swap(x[k], x[max_r]);
            }
            x[k]/=a[k][col];
            for(j=col+1; j<var; j++) a[k][j]/=a[k][col];
            a[k][col]=1;
            for(i=0;i<equ; i++)
            if(i!=k){
                x[i]-=x[k]*a[i][col];
                for(j=col+1; j<var; j++) a[i][j]-=a[k][j]*a[i][col];
                a[i][col]=0;
            }
        }
    
    
        return 0;
    }
    
    vector<int> G[110];
    int dgr[110];
    bitset<110> inf;
    int mp[110][110];
    
    int main(){
        int cas=0;
    
        while(~scanf("%d", &n) && n){
            memset(a, 0, sizeof a);
            memset(x, 0, sizeof x);
            memset(mp, 0, sizeof mp);
            inf.reset();
    
            for(int i=0; i<n; i++)
                G[i].clear(), dgr[i]=0, a[i][i]=-1;
            int u, v;
            while(scanf("%d%d", &u, &v)&&(u||v)){
                u--; v--;
                G[u].push_back(v);
                mp[u][v]=1;
                dgr[u]++;
            }
            equ=n, var=n;
            x[0]=-1;
            for(int i=0; i<n; i++){
                for(int j=0; j<G[i].size(); j++){
                    int v=G[i][j];
                    a[v][i]+=1./dgr[i];
                }
            }
    
            for(int k=0; k<n; k++)
                for(int i=0; i<n; i++)
                    for(int j=0; j<n; j++)
                        if(mp[i][k] && mp[k][j]) mp[i][j]=1;
    
            gauss();
    
            for(int i=0; i<n; i++){
                if(fabs(x[i])>eps && fabs(a[i][i])<eps) inf[i]=1;
                
                if(inf[i])
                for(int j=0; j<n; j++)
                    if(mp[i][j]) inf[j]=inf[i];
            }
    
            printf("Case #%d:\n", ++cas);
            int Q, p;
            scanf("%d", &Q);
            while(Q--){
                scanf("%d", &p);
                p--;
                if(inf[p])
                    puts("infinity");
                else{
                    printf("%.3lf\n", fabs(x[p]));
                }
            }
    
        }
    
        return 0;
    }

代码二：

#include<bits/stdc++.h>
    using namespace std;
    #define eps 1e-9
    const int MAXN=110;
    double a[MAXN][MAXN], x[MAXN];
    int equ, var;
    int n;
    
    int gauss(){
        int i, j, k, col, max_r;
        for(k=0, col=0; k<equ&&col<var; k++, col++){
            max_r=k;
            for(i=k+1; i<equ; i++)
                if(fabs(a[i][col])>fabs(a[max_r][col]))
                    max_r=i;
    
            if(fabs(a[max_r][col])<eps) return 0;
            if(k!=max_r){
                for(j=col; j<var; j++)
                    swap(a[k][j], a[max_r][j]);
                swap(x[k], x[max_r]);
            }
            x[k]/=a[k][col];
            for(j=col+1; j<var; j++) a[k][j]/=a[k][col];
            a[k][col]=1;
            for(i=0;i<equ; i++)
            if(i!=k){
                x[i]-=x[k]*a[i][col];
                for(j=col+1; j<var; j++) a[i][j]-=a[k][j]*a[i][col];
                a[i][col]=0;
            }
        }
    
    
        return 0;
    }
    
    vector<int> G[110];
    int dgr[110];
    bitset<110> inf;
    
    int main(){
        int cas=0;
        //freopen("E:/in.txt", "r", stdin);
        //freopen("E:/example.txt", "w", stdout);
        while(~scanf("%d", &n) && n){
            memset(a, 0, sizeof a);
            memset(x, 0, sizeof x);
            inf.reset();
    
            for(int i=0; i<n; i++)
                G[i].clear(), dgr[i]=0, a[i][i]=-1;
            int u, v;
            while(scanf("%d%d", &u, &v)&&(u||v)){
                u--; v--;
                G[u].push_back(v);
                dgr[u]++;
            }
            equ=n, var=n;
            x[0]=-1;
            for(int i=0; i<n; i++){
                for(int j=0; j<G[i].size(); j++){
                    int v=G[i][j];
                    a[v][i]+=1./dgr[i];
                }
            }
            gauss();
    
            for(int i=n-1; i>=0; i--){
                if(fabs(x[i])>eps && fabs(a[i][i])<eps) inf[i]=1;
                for(int j=i+1; j<n; j++) if(fabs(a[i][j])>eps && inf[j]) inf[i]=1;
            }
    
            printf("Case #%d:\n", ++cas);
            int Q, p;
            scanf("%d", &Q);
            while(Q--){
                scanf("%d", &p);
                p--;
                if(inf[p])
                    puts("infinity");
                else{
                    printf("%.3lf\n", fabs(x[p]));
                }
            }
    
        }
    
        return 0;
    }
    /*
    3
    1 3
    3 2
    0 0
    3
    1
    2
    3
    
    5
    1 2
    3 5
    2 4
    3 1
    4 2
    2 3
    4 5
    0 0
    5
    1
    2
    3
    4
    5
    
    
    */

[Link 1]: https://cn.vjudge.net/problem/UVA-10828