BZOJ 3143 HNOI2013 游走 高斯消元 期望

這道題是我第一次使用高斯消元解決期望類的問題，首發A了，感覺爽爽的....

不過筆者在做完后發現了一些問題，在原文的后面進行了說明。

?

中文題目，就不翻大意了，直接給原題：

　　一個無向連通圖，頂點從1編號到N，邊從1編號到M。?

　　小Z在該圖上進行隨機游走，初始時小Z在1號頂點，每一步小Z以相等的概率隨機選 擇當前頂點的某條邊，沿著這條邊走到下一個頂點，獲得等于這條邊的編號的分數。當小Z 到達N號頂點時游走結束，總分為所有獲得的分數之和。?

　　現在，請你對這M條邊進行編號，使得小Z獲得的總分的期望值最小。

　　輸出最小的總分期望值。

?

Solution:

　　這題貪心很明顯，哪條邊走過次數的期望最大，它就應該獲得最小的編號。

　　所以假設我們已經求出了每條邊走過的期望，我們就可以給它們并編上號了。

　　怎么算出每條邊走過的期望呢？

　　每條邊連接著兩個點u,v，很明顯的，當我們經過這條邊，一定是從兩個點中的某一個進入。

　　所以走過邊l的期望=走過u點的期望次數*從u點走到l上的概率+走過v點的期望次數*從v點走到l上的概率 （其中從i點走到它連接邊的概率為1/d[i]，d[i]為i的度數）

　　即：E[l]=e[u]/d[u]+e[v]/d[v]

　　可是我們只知道e[n]=0。但我們還知道這些點之間哪些是連通的，從而可以得出它們之間的關系：

　　

　　我們就可以利用這些點之間的關系建立起方程組，從而使用高斯消元求解。

　　別忘了，點求解完還要帶回到每條邊上去哦....

　　

　　附Bzoj上的AC代碼（codevs上過不了...我也不知道為什么...）

　　

/*
  Problem : Bzoj 3143 概率 & 高斯消元 
  Author : Robert Yuan
  Memory : 15604 kb
  Time : 628 MS    
  Result : Accept
*/
#include <cmath> 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;

#define maxn 520

struct Node{
    int data,next;
}node[maxn*maxn<<1];

struct Edge{
    int u,v;
    double w;
}edge[maxn*maxn<<1];

#define now node[point].data
#define then node[point].next

int n,m,cnt;
int head[maxn],deg[maxn];
const double eps=1e-6;
double w[maxn][maxn],rec_x[maxn],ans;

bool cmp(const Edge A,const Edge B){
    return A.w>B.w;
}

inline int in(){
    int x=0;char ch=getchar();
    while(ch>'9' || ch<'0') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}

void add(int u,int v){
    node[++cnt].data=v;node[cnt].next=head[u];deg[u]++;head[u]=cnt;
    node[++cnt].data=u;node[cnt].next=head[v];deg[v]++;head[v]=cnt;
}

void prework(){
    n=in();m=in();
    int u,v;
    for(int i=1;i<=n;i++) head[i]=-1;
    for(int i=1;i<=m;i++)
        u=in(),v=in(),edge[i].u=u,edge[i].v=v,add(u,v); 
    int point;
    for(int i=1;i<=n;i++){
        w[i][i]=1;
        point=head[i];
        while(point!=-1){
            w[i][now]=-(double)1/deg[now];
            point=then;
        }
    }
    w[1][n+1]=1;
}

void Swap(int i,int j,int x){
    double t;
    for(int k=x+1;k<=n+1;k++)
        t=w[i][k],w[i][k]=w[j][k],w[j][k]=t;
}

void gauss(){
    int i,j;
    for(i=1,j=1;i<=n && j<=n;i++,j++){
        int max_r=i;
        for(int k=i+1;k<=n;k++)
            if(fabs(w[max_r][j])+eps<fabs(w[k][j]))
                max_r=k;
        if(fabs(w[max_r][j])<eps){i--;continue;}
        if(max_r!=i) Swap(i,max_r,j);
        for(int k=i+1;k<=n;k++){
            double rate=w[k][j]/w[i][j];
            w[k][j]=0;
            for(int l=j+1;l<=n+1;l++)
                w[k][l]-=w[i][l]*rate;
        }
    }
    
    for(int i=n;i>=1;i--)
        if(fabs(w[i][i])>eps){
            double ans_c=w[i][n+1];
            for(int k=i+1;k<=n;k++)
                ans_c-=w[i][k]*rec_x[k];
            rec_x[i]=ans_c/w[i][i];
        }
}

void mainwork(){
    gauss();
    for(int i=1;i<=m;i++){
        edge[i].w=rec_x[edge[i].u]/deg[edge[i].u]+rec_x[edge[i].v]/deg[edge[i].v];
    }    
    sort(edge+1,edge+m+1,cmp);
    for(int i=1;i<=m;i++)
        ans+=edge[i].w*i;
    printf("%.3lf",ans);
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("x.in","r",stdin);
#endif
    prework();
    mainwork();
    return 0;
}

?

?

[以下是筆者后來發現的問題]

　　首先感謝某位不愿意透露姓名的人堆同學復制了我的代碼，然后代入了樣例，結果：

　　

　　然后第三行是無解？可是答案卻能跑出來...于是我傻了...開始胡亂吹逼[畢竟這么久沒打了...]

　　

　　好吧，然后各種逼都被打敗了...(●—●)

　　只能認真看看到底出了什么問題，于是發現這個式子有奧妙：

　　

　　左邊的e[i]表示走到i點的期望，右邊的e[j]表示走出j點的期望。

　　“走到”和“走出”卻并不是一樣的！

　　我們設e[i]表示走到i點的概率,e'[i]表示走出i點的概率。

　　如果說i!=n那么走到就能走出,e[i]=e'[i]；

　　如果i==n那么就有e'[n]=0,e[n]=1他們倆不同...盡管都已知，而我們列式子的時候，將e'[n]作為未知數帶進別的點的式子里，但在n自己的式子中卻用的是e[n]，導致兩個變量混淆。

　　所以鑒于e'[n]=0，就將建立方程部分修改了一下：

　　

　　于是現在的式子就發生了變化，最后化出來的矩陣也變成了正常的樣子：

　　

　　這樣解出來的就是e[n]是到達n點的期望=1，當然在給邊設定權值的時候，我們用的都是e'[i]，所以我們手動修改一下e'[n]=0就好了...

　　下面是修改過后的代碼：

#include <cmath> 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>using namespace std;#define maxn 520struct Node{int data,next;
}node[maxn*maxn<<1];struct Edge{int u,v;double w;
}edge[maxn*maxn<<1];#define now node[point].data
#define then node[point].nextint n,m,cnt;
int head[maxn],deg[maxn];
const double eps=1e-6;
double w[maxn][maxn],rec_x[maxn],ans;bool cmp(const Edge A,const Edge B){return A.w>B.w;
}inline int in(){int x=0;char ch=getchar();while(ch>'9' || ch<'0') ch=getchar();while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x;
}void add(int u,int v){node[++cnt].data=v;node[cnt].next=head[u];deg[u]++;head[u]=cnt;node[++cnt].data=u;node[cnt].next=head[v];deg[v]++;head[v]=cnt;
}void prework(){n=in();m=in();int u,v;for(int i=1;i<=n;i++) head[i]=-1;for(int i=1;i<=m;i++)u=in(),v=in(),edge[i].u=u,edge[i].v=v,add(u,v); int point;for(int i=1;i<=n;i++){w[i][i]=1;point=head[i];while(point!=-1){if(now!=n) w[i][now]=-(double)1/deg[now];else w[i][now]=0;point=then;}}w[1][n+1]=1;
}void Swap(int i,int j,int x){double t;for(int k=x+1;k<=n+1;k++)t=w[i][k],w[i][k]=w[j][k],w[j][k]=t;
}void gauss(){int i,j;for(i=1,j=1;i<=n && j<=n;i++,j++){int max_r=i;for(int k=i+1;k<=n;k++)if(fabs(w[max_r][j])+eps<fabs(w[k][j]))max_r=k;if(fabs(w[max_r][j])<eps){i--;continue;}if(max_r!=i) Swap(i,max_r,j);for(int k=i+1;k<=n;k++){double rate=w[k][j]/w[i][j];w[k][j]=0;for(int l=j+1;l<=n+1;l++)w[k][l]-=w[i][l]*rate;}}for(int i=n;i>=1;i--)if(fabs(w[i][i])>eps){double ans_c=w[i][n+1];for(int k=i+1;k<=n;k++)ans_c-=w[i][k]*rec_x[k];rec_x[i]=ans_c/w[i][i];}rec_x[n]=0;
}void mainwork(){gauss();for(int i=1;i<=m;i++){edge[i].w=rec_x[edge[i].u]/deg[edge[i].u]+rec_x[edge[i].v]/deg[edge[i].v];}    sort(edge+1,edge+m+1,cmp);for(int i=1;i<=m;i++)ans+=edge[i].w*i;printf("%.3lf",ans);
}int main(){
#ifndef ONLINE_JUDGEfreopen("x.in","r",stdin);
#endifprework();mainwork();return 0;
}

?

最后再次鳴謝人堆同學提出的問題，有問題才有進步嘛，歡迎大家提問哦...