[bzoj3143]:[Hnoi2013]游走

[bzoj3143]:[Hnoi2013]游走

Description

一个无向连通图,顶点从1编号到N,边从1编号到M。
小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束,总分为所有获得的分数之和。
现在,请你对这M条边进行编号,使得小Z获得的总分的期望值最小。

Hint

$N \leq 500$


Solution

现在怎么都是 数组开小 WA 而不是 RE

大概是访问到某个奇怪的内存去了?

求得每一个边经过的概率然后贪心即可
每个边的话求得点经过的概率即可

我们有 $E_1-\sum \frac {E_i} {d_i} =1$
$E_x-\sum \frac {E_i} {d_i} =0$
$E_n = 0$ 因为n节点不会对答案产生贡献

loj真TM好用


Code

#include<cstdio>
#include<cmath>
#include<cctype>
#include<cstring>
#include<algorithm>

using namespace std;

const double eps = 1e-8;
const int N = 505;
const int M = 250005;
double a[N][N], E[N], p[M], d[N];
int n, m;
int u[M], v[M];
int head[N];
struct Edge {
    int nxt, to;
}edg[M << 1];
double ans;

inline int read() {
    char c = getchar(); int x = 0;
    while(!isdigit(c)) c = getchar();
    do {
        x = x * 10 + (c ^ 48);
        c = getchar();
    } while(isdigit(c));
    return x;
}

void add(int from, int to) {
    static int cnt = 0;
    edg[++cnt] = (Edge) {head[from], to};
    head[from] = cnt;
}

void gause() {
    for(int i = 1; i <= n; ++i) {
        int p = i;
        for(int j = i + 1; j <= n; ++j) 
            if(fabs(a[j][i]) > fabs(a[p][i])) 
                p = j;
        if(p != i) 
            for(int j = 1; j <= n + 1; ++j)
                swap(a[i][j], a[p][j]);
        for(int j = i + 1; j <= n; ++j) {
            double radio = a[j][i] / a[i][i];
            for(int k = i; k <= n + 1; ++k)
                a[j][k] -= radio * a[i][k];
        }
    }
    for(int i = n; i; --i) {
        for(int j = n; j > i; --j)
            a[i][n + 1] -= E[j] * a[i][j];
        E[i] = a[i][n + 1] / a[i][i];
    }
}

int main() {
    n = read(), m = read();
    memset(head, -1, sizeof(head));
    for(int i = 1; i <= m; ++i) {
        u[i] = read(), v[i] = read();
        d[u[i]] += 1.0; d[v[i]] += 1.0;
        add(u[i], v[i]);
        add(v[i], u[i]);

    }
    for(int i = 1; i < n; ++i) {
        a[i][i] = 1;
        for(int j = head[i]; ~j; j = edg[j].nxt) 
            if(!edg[j].to != n) {
                a[i][edg[j].to] -= 1.0 /  d[edg[j].to];
            }
    }
    a[n][n] = 1;
    a[1][n + 1] = 1;
    gause();
    for(int i = 1; i <= m; ++i)
        p[i] = E[u[i]] / d[u[i]] + E[v[i]] / d[v[i]];
    sort(p + 1, p + m + 1);
    for(int i = 1; i <= m; ++i)
        ans += p[i] * (m - i + 1);
    printf("%.3f\n", ans);
    return 0;
}

说点什么

avatar
  Subscribe  
提醒