【BZOJ1491】【NOI2007】社交网络

挺简单的floyd

// <1491.cpp> - 01/04/17 21:36:25
// 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=110;
const int INF=1e9;
int d[MAXN][MAXN];
lol c[MAXN][MAXN];
int main(){
    int n=gi(),m=gi();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)d[i][j]=INF;
    for(int i=1;i<=m;i++){
        int x=gi(),y=gi();
        d[x][y]=d[y][x]=gi();
        c[x][y]=c[y][x]=1;
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                if(d[i][k]+d[k][j]<d[i][j])d[i][j]=d[i][k]+d[k][j],c[i][j]=0;
                if(d[i][k]+d[k][j]==d[i][j])c[i][j]+=c[i][k]*c[k][j];
            }
    for(int k=1;k<=n;k++){
        double I=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                if(k==i||k==j||i==j)continue;
                if(d[i][k]+d[k][j]!=d[i][j])continue;
                I+=double(c[i][k])*c[k][j]/c[i][j];
            }
        printf("%.3lf\n",I);
    }
    return 0;
}

// <1491.cpp> - 01/04/17 21:36:25

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

const int INF=1e9;

int d[MAXN][MAXN];

lol c[MAXN][MAXN];

int main(){

int n=gi(),m=gi();

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)d[i][j]=INF;

for(int i=1;i<=m;i++){

int x=gi(),y=gi();

d[x][y]=d[y][x]=gi();

c[x][y]=c[y][x]=1;

}

for(int k=1;k<=n;k++)

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++){

if(d[i][k]+d[k][j]<d[i][j])d[i][j]=d[i][k]+d[k][j],c[i][j]=0;

if(d[i][k]+d[k][j]==d[i][j])c[i][j]+=c[i][k]*c[k][j];

}

for(int k=1;k<=n;k++){

double I=0;

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++){

if(k==i||k==j||i==j)continue;

if(d[i][k]+d[k][j]!=d[i][j])continue;

I+=double(c[i][k])*c[k][j]/c[i][j];

}

printf("%.3lf\n",I);

}

return 0;

}