很经典的高斯消元题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
// <3143.cpp> - Wed Aug 24 09:55:36 2016 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=510; const int MAXM=300010; const int INF=1e9; int n,m; double a[MAXN][MAXN]; void gauss(){ for(int i=1;i<=n;i++){ for(int k=i+1;k<=n;k++)if(abs(a[k][i])>abs(a[i][i]))swap(a[k],a[i]); for(int j=n+1;j>=i;j--)a[i][j]/=a[i][i]; for(int k=1;k<=n;k++){ if(k==i)continue; for(int j=n+1;j>=i;j--)a[k][j]-=a[k][i]*a[i][j]; } } } int u[MAXM],v[MAXM],d[MAXN]; double f[MAXM]; int main(){ n=gi(),m=gi(); for(int i=1;i<=m;i++){ d[u[i]=gi()]++,d[v[i]=gi()]++; if(u[i]!=n)a[u[i]][u[i]]++; if(v[i]!=n)a[v[i]][v[i]]++; if(u[i]!=n&&v[i]!=n)a[u[i]][v[i]]--,a[v[i]][u[i]]--; } a[1][n--]=1; gauss(); for(int i=1;i<=m;i++)f[i]=a[u[i]][n+1]+a[v[i]][n+1]; sort(f+1,f+m+1); double ans=0; for(int i=m;i;i--)ans+=f[i]*(m-i+1); printf("%.3lf",ans); return 0; } |
说点什么