题目链接

题意分析

我们计算出每一条边经过的概率是多少

然后概率大的边编号小

怎么计算概率 是一个问题

首先 我们存在一条边

这条边的两个端点是\(u,v\)

经过两个端点的概率分别是\(p_u,p_v\)

这两个端点链接的边数分别是\(d_u,d_v\)

那么经过这条边的概率就是\(\frac{p_u}{d_u}+\frac{p_v}{d_v}\)

怎么计算经过一个点的概率 ？

\[p_i=\begin{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
#include
#include
#include
#include
#include
#include
#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 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;i0;--i)
	{
		for(int j=i+1;j