[HNOI2013]游走

Posted by Panda2134's Blog on March 15, 2018

题意

一个无向简单连通图,边权为 $1\dots m$ 的整数。问分配边权后,从点 1 随机游走到点 $n$ 的最小期望距离。

思路

刚看完《训练指南》上面的矩阵一部分,做一做相关省选题练练手,结果第一题就不会做……

这是最开始的错误思路:

我们对每个点显然可以列出递推式,设 $a_u$ 为点 1 走到点 $u$ 的期望距离。那么一定有:

为什么?我们考虑是从哪个点 $v_i$ 沿着边 $<v_i, u>$ 走到 $u$ 的。对于沿着每一条边 $<v_i, u>$ 走到 $u$ 点的情况,由全期望公式知,对应的期望值为 $a_{v_i} + w_{<v_i, u>}$ . 所有情况加权平均即为上式。

但是我们并不知道每条边的长度啊?!这样就不能做了……

我们换个思路:不妨写出每个点期望经过的次数 $b_u$ ,则

为什么是除以 $\deg v$ 呢?不要忘了,每个点的期望经过次数等于 邻接弧 期望经过次数之和。而对于每条和 $u$ 邻接的弧 $<u, v>$ ,经过它到 $u$ 的次数都是 $b_v / \deg v$ ,因为到达邻接点 $v$ 的期望次数为 $b_v$ ,而又有 $ 1 / \deg v$ 的概率经过弧 $<v, u>$ ,根据期望定义和全期望公式,可得上式。

我们再来考虑不限定经过方向的前提下,每条弧的期望经过次数 $c_{<u, v>}$。显然有:

则答案为

等等…… $\sum_i a_i b_i$ 求最值?这不就是排序不等式么……

先高斯消元求 ${b_n}$ ,再利用逆序和最小安排权值即可。由于是无向连通图,一定有解。

这个题目中,我学到了几点:

  1. 一定要灵活利用好期望的线性、全期望公式,更别忘了期望的定义式。
  2. 点和边的对偶转化是很方便的。如果要求边相关期望,而点的期望更好求(一般都是这样),可以进行转化。
  3. 最优化问题有时候可以用不等式解决。

代码

注意实现的一些细节,调了好久没调出来,看了Sengxian的题解才知道:

  1. 对于点 1 ,不能漏掉最开始的一次经过,也就是经过次数的期望要加上 1 。按照《训练指南》的说法,可以看成从虚拟的节点 0 以 1 的概率转移而来。
  2. 对于点 $n$ ,由于到了它就不再继续游走,比较特殊,我们不对它列方程解期望;对于一端是 $n$ 的弧,我们只考虑向 $n$ 的方向走的期望次数。
#include <bits/stdc++.h>   
#define fst first    
#define snd second    
using namespace std;    

const int MAXN = 1000;
const double eps = 1e-8;

struct Edge { int v, next; };

int n, m, e_ptr = 1, deg[MAXN+10], head[MAXN+10]; Edge E[(MAXN*MAXN+10)<<1];
double b[MAXN+10][MAXN+10], c[(MAXN*MAXN+10)<<1]; 
vector<pair<int, int> > E0;

inline int dcmp(double x) {
    return fabs(x) < eps ? 0 : (x > 0 ? 1 : -1);
}

void AddEdge(int u, int v) {
    E[++e_ptr] = (Edge) { v, head[u] }; head[u] = e_ptr;
}

void AddPair(int u, int v) {
    AddEdge(u, v); AddEdge(v, u);
    deg[u]++; deg[v]++;
    E0.push_back(make_pair(u, v));
}

void Init() {
    int u, v;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++) {
        scanf("%d%d", &u, &v);
        AddPair(u, v);
    }
}

void Gauss(int n, double A[MAXN+10][MAXN+10]) {
    for(int i = 1; i <= n; i++) {
        int r = i;
        for(int j = i+1; j <= n; j++)
            if(fabs(A[j][i]) > fabs(A[r][i])) r = j;
        if(r != i)
            for(int j = 1; j <= n+1; j++)
                swap(A[i][j], A[r][j]);
        
        for(int k = i+1; k <= n; k++) {
            double t = A[k][i] / A[i][i];
            for(int j = 1; j <= n+1; j++)
                A[k][j] -= t * A[i][j];
        }
    }
    for(int i = n; i >= 1; i--) {
        for(int j = i+1; j <= n; j++)
            A[i][n+1] -= A[i][j] * A[j][n+1];
        A[i][n+1] /= A[i][i];
    }
}

void Work() {
    double ans = 0;
    for(int u = 1; u <= n-1; u++) {
        b[u][u] = 1;
        for(int j=head[u]; j; j=E[j].next) {
            int v = E[j].v;
            if(v == n) continue;
            b[u][v] = (-1.0) / deg[v];
        }
        b[u][n] = bool(u == 1);
    }
    Gauss(n-1, b); // n-1个方程, n-1个变量
    for(int i = 0; i < m; i++) {
        pair<int, int> &e = E0[i];
        double p = (e.fst != n ? b[e.fst][n] / deg[e.fst] : 0.0);
        double q = (e.snd != n ? b[e.snd][n] / deg[e.snd] : 0.0);
        c[i] = p + q;
    }
    sort(c, c + m);
    for(int i = 0; i < m; i++)
        ans += c[i] * (m-i);
    printf("%.3lf", ans);
}

int main() {
    Init(); Work();
    return 0;
}