3143: [Hnoi2013]游走
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1026 Solved: 448
[Submit][Status]
Description
一个无向连通图，顶点从1编号到N，边从1编号到M。
小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选 择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束，总分为所有获得的分数之和。
现在，请你对这M条边进行编号，使得小Z获得的总分的期望值最小。
Input
第一行是正整数N和M，分别表示该图的顶点数 和边数，接下来M行每行是整数u，v(1≤u,v≤N)，表示顶点u与顶点v之间存在一条边。 输入保证30%的数据满足N≤10，100%的数据满足2≤N≤500且是一个无向简单连通图。
Output
仅包含一个实数，表示最小的期望值，保留3位小数。
Sample Input
3 3
2 3
1 2
1 3
2 3
1 2
1 3
Sample Output
3.333
HINT
边(1,2)编号为1，边(1,3)编号2，边(2,3)编号为3。
这道题我又把题目看错了，我最开始看成了有向无环图，【目测世纪大水题】。。。
当这种期望题出现环之后，就变的复杂很多，我们可以对于每一个点求出它的期望经过次数p[]，则p[i]=segma(p[j]/d[j])，有一点还是有点不清楚，就是为什么p[1]在上述式子上必须恰好加1，就只好姑且先记住这样的结论吧。
有了上述思路，就可以用高斯消元来做了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 1000
#define MAXV MAXN
#define MAXE 500000
#define abs(x) ((x)>0?(x):(-(x)))
typedef long double real;
struct Edge
{
int np;
Edge *next;
}E[MAXE],*V[MAXV];
int tope=-;
void addedge(int x,int y)
{
E[++tope].next=V[x];
E[tope].np=y;
V[x]=&E[tope];
}
int deg[MAXN];
int q[MAXN];
real pp[MAXN];
real a[MAXN][MAXN];
int n,m;
struct edge
{
int x,y;
real p;
}w[MAXE];
bool cmp_p(edge e1,edge e2)
{
return e1.p>e2.p;
}
void pm()
{
for (int i=;i<n;i++)
{
for (int j=;j<=n;j++)
{
printf("%.2Lf ",a[i][j]);
}
printf("\n");
}
printf("\n");
}
int main()
{
freopen("input.txt","r",stdin);
int i,j,k,x,y,z;
scanf("%d%d",&n,&m);
for (i=;i<m;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
deg[x]++;deg[y]++;
w[i].x=x;w[i].y=y;
}
int now;
Edge *ne;
for (i=;i<=n-;i++)
{
now=i;
for (ne=V[now];ne;ne=ne->next)
{
if (ne->np!=n)
a[now][ne->np]=1.0/deg[ne->np];
}
a[now][now]=-;
a[now][n]=;
}
a[][n]=;
//pm();
for (i=;i<=n-;i++)
{
x=i;
for (j=i+;j<=n-;j++)
{
if (abs(a[j][i])>abs(a[x][i]))
{
x=j;
}
}
if (x!=i)
{
for (j=i;j<=n;j++)
{
swap(a[i][j],a[x][j]);
}
}
if (!a[i][i])continue;
for (j=i+;j<=n-;j++)
{
real t=a[j][i]/a[i][i];
for (k=i;k<=n;k++)
{
a[j][k]-=t*a[i][k];
}
}
//pm();
}
pp[n]=;
for (i=n-;i>=;i--)
{
for (j=i+;j<=n;j++)
{
pp[i]-=pp[j]*a[i][j];
}
pp[i]/=a[i][i];
}
pp[n]=;
/* for (i=1;i<=n;i++)
printf("%.2Lf ",pp[i]);
printf("\n");*/
for (i=;i<m;i++)
{
w[i].p=pp[w[i].x]/deg[w[i].x] + pp[w[i].y]/deg[w[i].y];
}
sort(w,w+m,cmp_p);
int head=-,tail=-;
real ans=;
for (i=;i<m;i++)
{
ans+=(i+)*w[i].p;
}
printf("%.3Lf",ans);
}