bzoj 3143: [Hnoi2013]游走 高斯消元

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

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);
}
上一篇:调式WP程序报0x80131500错误的解决办法


下一篇:linux使用Nginx搭建静态资源服务器