#D10052. 「NOI2007」社交网络
前言(Front talk)
网址(Website)
题目(Problem)
输入格式
在无向图中,我们将所有结点从
注意任意两个结点之间最多有一条无向边相连,无向图中也不会出现自环(即不存在一条无向边的两个端点是相同的结点)。
输出格式
样例 #1
样例输入 #1
4 4
1 2 1
2 3 1
3 4 1
4 1 1
样例输出 #1
1.000
1.000
1.000
1.000
提示
题解(Solution)
For(k,1,n) For(i,1,n) For(j,1,n){//O(n^3)
if(mp[i][k]==inf && mp[k][j]==inf) continue;
if(mp[i][j]>mp[i][k]+mp[k][j]){
ed[i][j]=ed[i][k]*ed[k][j];
mp[i][j]=mp[i][k]+mp[j][k];
}else if(mp[i][j]==mp[i][k]+mp[k][j]){
ed[i][j]+=ed[i][k]*ed[k][j];
}
}
For(k,1,n) For(i,1,n) For(j,1,n){
if(i==j || j==k || k==i) continue;
if(mp[i][j]==mp[i][k]+mp[k][j]){
ans[k]+=1.0*ed[i][k]*ed[k][j]/ed[i][j];
}
}
代码(Code)
#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 105;
int mp[N][N],ed[N][N];
double ans[N];
int n,m;
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
memset(mp,0x3f,sizeof mp);
cin>>n>>m;For(i,1,m){
int x=input(),y=input(),v=input();
mp[x][y]=mp[y][x]=v;
ed[x][y]=ed[y][x]=1;
}For(k,1,n) For(i,1,n) For(j,1,n){//O(n^3)
if(mp[i][k]==inf && mp[k][j]==inf) continue;
if(mp[i][j]>mp[i][k]+mp[k][j]){
ed[i][j]=ed[i][k]*ed[k][j];
mp[i][j]=mp[i][k]+mp[j][k];
}else if(mp[i][j]==mp[i][k]+mp[k][j]){
ed[i][j]+=ed[i][k]*ed[k][j];
}
}For(k,1,n) For(i,1,n) For(j,1,n){
if(i==j || j==k || k==i) continue;
if(mp[i][j]==mp[i][k]+mp[k][j]){
ans[k]+=1.0*ed[i][k]*ed[k][j]/ed[i][j];
}
}For(i,1,n) printf("%.3lf\n",ans[i]);
return 0;
}