【BZOJ3143】【HNOI2013】游走

很经典的高斯消元题

// <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;
}

// <3143.cpp> - Wed Aug 24 09:55:36 2016

// This file is created by XuYike's black technology automatically.

// 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;

}