题目链接
题意分析
我们计算出每一条边经过的概率是多少
然后概率大的边编号小
怎么计算概率 是一个问题
首先 我们存在一条边
这条边的两个端点是(u,v)
经过两个端点的概率分别是(p_u,p_v)
这两个端点链接的边数分别是(d_u,d_v)
那么经过这条边的概率就是(frac{p_u}{d_u}+frac{p_v}{d_v})
怎么计算经过一个点的概率 ？
[p_i=egin{cases}
sum_{∃(u,i)∈E}frac{p_u}{d_u}+1 (i=1)\
sum_{∃(u,i)∈E}frac{p_u}{d_u} (1＜i＜n)\
0 (i=n)
end{cases}
]
具体怎么计算 如果使用图论的遍历的话 存在环的情况会特别难搞 而顺序的话也不好处理
但是我们发现对上述状态转移方程加以转化的话 就成了线性方程组
那么我们就可以考虑一下 使用高斯消元法解一下 然后的话就可以求边边 然后编号了
CODE:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define N 510
#define M 1250080
using namespace std;
int n,m;
int in[N];
struct Node
{
int u,v,id;
double pi;
friend bool operator < (const Node &A,const Node &B)
{return A.pi>B.pi;}
}e[M];
double num[N][N],ans[N];
double lastans;
vector<int> G[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)
{
scanf("%d%d",&e[i].u,&e[i].v);
in[e[i].u]++;in[e[i].v]++;
G[e[i].u].push_back(e[i].v);
G[e[i].v].push_back(e[i].u);
}
for(int i=1;i<n;++i)
{
if(i==1) num[1][n]=1;
for(int j=0;j<(int)G[i].size();++j)
{
if(G[i][j]==n) continue;
num[i][G[i][j]]=-1.0/(double)in[G[i][j]];
}
num[i][i]=1.0;
}
// for(int i=1;i<n;++i)
// for(int j=1;j<=n;++j)
// printf("%.3lf%c",num[i][j],(j==n ? '
':' '));
for(int k=1;k<n;++k)
{
int nowtmp=k;
for(int i=k+1;i<n;++i)
if(fabs(num[nowtmp][k])<fabs(num[i][k])) nowtmp=i;
swap(num[nowtmp],num[k]);
double tmp=num[k][k];
for(int i=k;i<=n;++i) num[k][i]/=tmp;
for(int i=k+1;i<n;++i)
{
tmp=num[i][k];
for(int j=k;j<=n;++j) num[i][j]-=num[k][j]*tmp;
}
}
// for(int i=1;i<n;++i)
// for(int j=1;j<=n;++j)
// printf("%.3lf%c",num[i][j],(j==n ? '
':' '));
for(int i=n-1;i>0;--i)
{
for(int j=i+1;j<n;++j) num[i][n]-=num[i][j]*ans[j];
ans[i]=num[i][n];
}
// for(int i=1;i<=n;++i) printf("%.3lf%c",ans[i],(i==n ? '
':' '));
for(int i=1;i<=m;++i) e[i].pi=(ans[e[i].u]/(double)in[e[i].u]+ans[e[i].v]/(double)in[e[i].v]);
sort(e+1,e+m+1);
for(int i=1;i<=m;++i)
lastans+=(double)i*e[i].pi;
printf("%.3lf
",lastans);
return 0;
}