[NOI2007]社交网络

第一行有两个整数，n和m，表示社交网络中结点和无向边的数目。在无向图中，我们将所有结点从1到n进行编号。

接下来m行，每行用三个整数a, b, c描述一条连接结点a和b，权值为c的无向边。注意任意两个结点之间最多有一条无向边相连，无向图中也不会出现自环（即不存在一条无向边的两个端点是相同的结点）。

C++14(g++5.4) 解法, 执行用时: 13ms, 内存消耗: 624K, 提交时间: 2020-02-15 11:46:52

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int mp[105][105];
ll cnt[105][105];
int main(){
    int n,m,x,y,c;
    scanf("%d%d",&n,&m);
    memset(mp,0x3f,sizeof(mp));
    for(int i=0;i<m;++i){
        scanf("%d%d%d",&x,&y,&c);
        mp[x][y]=mp[y][x]=min(mp[x][y],c);
        cnt[x][y]=cnt[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(mp[i][j]>mp[i][k]+mp[k][j]){
                    mp[i][j]=mp[i][k]+mp[k][j];
                    cnt[i][j]=cnt[i][k]*cnt[k][j];
                }
                else if(mp[i][j]==mp[i][k]+mp[k][j])
                    cnt[i][j]+=cnt[i][k]*cnt[k][j];
    double ans;
    for(int k=1;k<=n;++k){
        ans=0;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                if(i!=k&&j!=k&&i!=j)
                    ans+=(double)(mp[i][k]+mp[k][j]==mp[i][j]?cnt[i][k]*cnt[k][j]:0)/cnt[i][j];
        printf("%.3f\n",ans);
    }
    return 0;
}

C++(clang++11) 解法, 执行用时: 14ms, 内存消耗: 512K, 提交时间: 2020-10-21 22:14:50

#include<bits/stdc++.h>
#define LL long long
#define db double
using namespace std;
const int N=105;
int n,m,g[N][N];LL dp[N][N];
void upd(int u,int v,int w,LL x){if(g[u][v]>w)g[u][v]=w,dp[u][v]=x;else if(g[u][v]==w)dp[u][v]+=x;}
int main(){
	memset(g,0x3f,sizeof(g));
	scanf("%d%d",&n,&m);
	for(int i=1,u,v,w;i<=m;i++)
		scanf("%d%d%d",&u,&v,&w),upd(u,v,w,1),upd(v,u,w,1);
	for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
		if(i!=j&&i!=k&&j!=k)upd(i,j,g[i][k]+g[k][j],(LL)dp[i][k]*dp[k][j]);
	for(int k=1;k<=n;k++){
		db ans=0;LL fz,fm;
		for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
			if(i!=j&&i!=k&&j!=k){
				if(g[i][k]+g[k][j]==g[i][j])fz=dp[i][k]*dp[k][j];else fz=0;
				fm=dp[i][j];ans+=(db)fz/fm;
			}
		printf("%.3lf\n",ans);
	}
	return 0;
}

详情