P3232 [HNOI2013]游走

\[\color{royalblue}{\huge\texttt{P3232 [HNOI2013]游走}} \]

---

\[f(x) \]

表示期望从 \(x\) 点离开的次数，

\[Num_e(x) \]

表示 \(x\) 点的出度，
则每条边期望被经过的次数为

\[{g(u,v)=\frac{f(u)}{Num_e(u)}+\frac{f(v)}{Num_e(v)}} \]

推dp柿子:

\[{f(x)=\sum_{v\in edge(x)} \frac{f(v)}{Num_e(v)}}\;,\;x \in (1,n). \]

\[{f(x)=\sum_{v\in edge(x)} \frac{f(v)}{Num_e(v)}+1}\;,\;x=1. \]

\[{f(x)=0\;,\;x=n.} \]

第一个柿子是说，对于 \((1,n)\) 这些点，进入它们后必然出去一次，所以 \(E(into\;\;x)=E(out\;of\;\;x)\).
第二个柿子，对于 \(1\) 号点，从它出发决定了它离开次数比进入次数大 \(1\).
第三个柿子，\(n\) 为终点，不会再离开了.

然后大力高斯消元，把边按期望经过次数排序，贪心选择.

code:

#include 
#define ri register int
#define g() getchar()
#define MAXN 502
#define pc(a) putchar(a)
#define Tp template
using namespace std;
namespace SlowIO
{
	Tp inline void rd(T &x)	{
		x=0;char i=g();bool f=1;
		while(!isdigit(i)) f&=(i!='-'),i=g();
		while(isdigit(i)) x=(x<<3)+(x<<1)+(i^48),i=g();
		x*=((f<<1)-1);
	}
	Tp inline void op(T x){
		if(x<0) pc('-'),x=-x;
		if(x>=10) op(x/10);
		pc(x%10+48);
	}
	Tp inline void writeln(T x){op(x);pc('\n');}
	Tp inline void writesp(T x){op(x);pc(' ');}
};
using namespace SlowIO;
int cntr,head[MAXN];
struct edge{
    int to,next;
}e[MAXN*MAXN];
inline void add(int u,int v){
    e[++cntr].to=v;
    e[cntr].next=head[u];
    head[u]=cntr;
}
int n,m;
int deg[MAXN];//每个点的出度
double a[MAXN][MAXN];
double f[MAXN];//期望从x点离开的次数 E(离开x)
double g[MAXN*MAXN];
double ass;//Asswer
//x∈(1,n),f[x]=E(进入x点);
//f[1]=E(进入1点)+1,f[n]=0.
//Gauss-Jordan
#define abs fabs
inline bool solve()
{
    ri sta;
    for(ri i=1;i<=n;i++)
    {
        sta=i;
        for(ri j=i+1;j<=n;j++)
        if(abs(a[j][i])>abs(a[sta][i]))
        sta=j;
        if(sta!=i)
        for(ri j=1;j<=n+1;j++)
        swap(a[sta][j],a[i][j]);
        if(!a[i][i]) return true;
        for(ri j=1;j<=n;j++)
        {
            if(j==i) continue;
            for(ri k=i+1;k<=n+1;k++)
            a[j][k]-=a[i][k]*a[j][i]/a[i][i];
        }
    }
    return false;
}

int main()
{
    rd(n),rd(m);
    static int u[MAXN*MAXN],v[MAXN*MAXN];
    //我焯 我为什么一直开的MAXN啊我sb吗()
    static int frm,tp;
    for(ri i=1;i<=m;i++)
    {
        rd(u[i]),rd(v[i]);
        add(u[i],v[i]),add(v[i],u[i]);
        deg[u[i]]++,deg[v[i]]++;
    }
    //我焯 真就遍历所有边呗 O(2m)>O(m)(暴论)
    a[1][n]=1;
    for(ri i=1;i<=n-1;i++)
    {
        a[i][i]=1.0;
        for(ri j=head[i];j;j=e[j].next)
        {
            int v=e[j].to;
            if(v==n) continue;
            a[i][v]=-1.0/deg[v];
        }
    }--n;solve();
    for(int i=1;i<=n;i++) f[i]=a[i][n+1]/a[i][i];
    for(ri i=1;i<=m;i++){
        frm=u[i],tp=v[i];
        g[i]+=(frm!=n+1)*f[frm]/deg[frm]+(tp!=n+1)*f[tp]/deg[tp];
    }
    sort(g+1,g+m+1);
    for(ri i=1;i<=m;i++) ass+=1.0*i*g[m-i+1];
    printf("%.3lf",ass);
    return 0;
}