救救我吧!大佬们!小萌新要崩溃啦!
查看原帖
救救我吧!大佬们!小萌新要崩溃啦!
289056
北射天狼楼主2023/7/26 17:07

是因为精度问题吗?qwq,我要疯啦!

#include <bits/stdc++.h>
using namespace std;
inline int read(){
	int s = 0,f = 1;char c = getchar();
	while (!isdigit(c)){if (c == '-')f = -1;c = getchar();}
	while (isdigit(c)){s = (s << 3) + (s << 1) + (c ^ 48);c = getchar();}
	return s*f;
}
const int N = 5e2 + 5;
const int M = 5e5 + 5;
int n,m,cnt,deg[N];
int head[N];
long double a[N][N],f[N],g[N];
long double ans = 0;
struct node{
    int v,next;
}tree[M<<1];
struct side{
	int u,v;
}edge[M];
void add(int u,int v){
	tree[++cnt].next = head[u];
	tree[cnt].v = v;
	head[u] = cnt;
}
long double c(long double p){
	return p>0?p:-p;
}
void Gauss_Yordan(){
	for (int i=1;i<n;i++){
		int maxn = i;
		for (int j=i+1;j<n;j++)
		    if (c(a[j][i]) > c(a[maxn][i]))
		        maxn = j;
		swap(a[maxn],a[i]);
		for (int j=1;j<n;j++){
			if (i == j)
			    continue;
			long double tmp = a[j][i] / a[i][i];//needed to be delete
			for (int k=i+1;k<=n;k++)//all the 
			    a[j][k] -= tmp * a[i][k];
		}
	}
	for (int i=1;i<n;i++)
	    g[i] = 1.0 * a[i][n] / a[i][i];
}
int main()
{
	//freopen("P3232_5.in","r",stdin);
    n = read(); m = read();
    for (int i=1,u,v;i<=m;i++){
    	u = read(); v = read();
    	edge[i].u = u; edge[i].v = v;
    	add(edge[i].u,edge[i].v);
    	add(edge[i].v,edge[i].u);
    	++deg[u],++deg[v];
	}
	for (int i=1;i<n;i++){
		a[i][i] = 1.0;
		for (int j = head[i];j;j=tree[j].next){
			int v = tree[j].v;
			if (v != n)
			    a[i][v] = -1.0 / deg[v];
		}
	}
	a[1][n] = 1.0;
	Gauss_Yordan();
	for (int i=1;i<=m;i++){
		int u = edge[i].u,v = edge[i].v;
		if (u != n)
		    f[i] += 1.0 * g[u] / deg[u] * 1.0;
		if (v != n)
		    f[i] += 1.0 * g[v] / deg[v] * 1.0;
	}
	sort(f+1,f+m+1);
    for (int i=1;i<=m;i++)
        ans += (long double)(m - i + 1)*1.0*f[i];
    printf("%.3Lf\n",ans);
	return 0;
}
2023/7/26 17:07
加载中...