首页 > 代码库 > BZOJ1491: [NOI2007]社交网络
BZOJ1491: [NOI2007]社交网络
1491: [NOI2007]社交网络
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 813 Solved: 479
[Submit][Status]
描述
在社交网络（social network）的研究中，我们常常使用图论概念去解释一些社会现象。
不妨看这样的一个问题。在一个社交圈子里有n个人，人与人之间有不同程度的关系。我们将这个关系网络对应到一个n个结点的无向图上，两个不同的人若互相认识，则在他们对应的结点之间连接一条无向边，并附上一个正数权值c，c越小，表示两个人之间的关系越密切。
我们可以用对应结点之间的最短路长度来衡量两个人s和t之间的关系密切程度，注意到最短路径上的其他结点为s和t的联系提供了某种便利，即这些结点对于s和t之间的联系有一定的重要程度。我们可以通过统计经过一个结点v的最短路径的数目来衡量该结点在社交网络中的重要程度。
考虑到两个结点A 和B 之间可能会有多条最短路径。我们修改重要程度的定义如下：
令Cs,t 表示从s 到t 的不同的最短路的数目，Cs,t(v)表示经过v从s到t的最短路的数目；则定义
I(v)=∑(s<>v,t<>v)Cs,t(v)/Cs,t
为结点v 在社交网络中的重要程度。
为了使I(v)和Cs,t(v)有意义，我们规定需要处理的社交网络都是连通的无向图，即任意两个结点之间都有一条有限长度的最短路径。现在给出这样一幅描述社交网络的加权无向图，请你求出每一个结点的重要程度。
格式
输入格式
输入文件中第一行有两个整数，n和m，表示社交网络中结点和无向边的数目。在无向图中，我们将所有结点从1 到n 进行编号。接下来m 行，每行用三个整数a,b,c描述一条连接结点a和b,权值为c的无向边。注意任意两个结点之间最多有一条无向边相连，无向图中也不会出现自环（即不存在一条无向边的两个端点是相同的结点）。
输出格式
输出文件包括n行，每行一个实数，精确到小数点后3位。第i行的实数表示结点i在社交网络中的重要程度。
Sample Input
1 2 1
2 3 1
3 4 1
4 1 1
Sample Output
1.000
1.000
1.000
HINT
n<=100 m<=4500 c<=1000
题解：
n<=100? n^3随便搞。
自然先floyed，根据题目意思，
我们用f[i][j]表示i 到 j 的最短路长度，g[i][j]表示 i 到 j 的最短路条数。
那么设当前枚举点为 i，再枚举 s和t，若有 f[s][i]+f[i][t]=f[s][t] 那么从s到t 经过i 的最短路条数就是 g[s][i]*g[i][t]
那么问题就转化成了 如何求 s到t 的最短路条数。
我自己yy了一个做法，如下：
1.把1……n放入一个数组中并且按s到它的最短路长度排序。
2.假设当前正在考虑 s 到 i 的最短路条数，那么显然只会有在i 前面的点对 g[s][i]有贡献。
那么我们枚举最后一条边，这样可以保证方案不重复。
即 若 f[s][j]+b[j][i]==f[s][i]，则 g[s][i]+=g[s][j] 其中b[j][i]表示初始时（没有floyed） j 到i 的路径长度
正确性是显然的
没开long long WA了一次。。。
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 500+10014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 using namespace std;22 inline int read()23 {24 int x=0,f=1;char ch=getchar();25 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}26 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}27 return x*f;28 }29 ll n,m,b[maxn][maxn],f[maxn][maxn],g[maxn][maxn];30 struct rec{int w,id;}a[maxn];31 inline bool cmp(rec a,rec b)32 {33 return a.w<b.w;34 }35 int main()36 {37 freopen("input.txt","r",stdin);38 freopen("output.txt","w",stdout);39 n=read();m=read();40 for1(i,n)41 for1(j,n)42 f[i][j]=inf>>1,b[i][j]=inf>>1;43 for1(i,n)f[i][i]=0;44 for1(i,m)45 {46 int x=read(),y=read(); 47 f[x][y]=f[y][x]=b[x][y]=b[y][x]=read();48 }49 for1(k,n)50 for1(i,n)51 for1(j,n)52 f[i][j]=min(f[i][j],f[i][k]+f[k][j]);53 memset(g,0,sizeof(g)); 54 for1(i,n)55 {56 for1(j,n)a[j].w=f[i][j],a[j].id=j;57 sort(a+1,a+n+1,cmp);58 g[i][i]=1; 59 for2(j,2,n)60 for1(k,j-1)61 if(f[i][a[k].id]+b[a[k].id][a[j].id]==f[i][a[j].id])62 g[i][a[j].id]+=g[i][a[k].id];63 }64 for1(i,n)65 {66 double ans=0; 67 for1(j,n)68 for1(k,n)69 if(j!=i&&k!=i&&j!=k&&f[j][i]+f[i][k]==f[j][k])70 ans+=double(g[j][i]*g[i][k])/double(g[j][k]);71 printf("%.3lf\n",ans); 72 } 73 return 0;74 }
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
我sb了，直接floyed的时候求出就行了。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
还是太弱了。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 500+10014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 using namespace std;22 inline int read()23 {24 int x=0,f=1;char ch=getchar();25 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}26 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}27 return x*f;28 }29 ll n,m,f[maxn][maxn],g[maxn][maxn];30 int main()31 {32 freopen("input.txt","r",stdin);33 freopen("output.txt","w",stdout);34 n=read();m=read();35 for1(i,n)36 for1(j,n)37 f[i][j]=inf>>1;38 for1(i,n)f[i][i]=0;39 for1(i,m)40 {41 int x=read(),y=read(); 42 f[x][y]=f[y][x]=read();43 g[x][y]=g[y][x]=1;44 }45 for1(k,n)46 for1(i,n)47 for1(j,n)48 {49 if(i==j||j==k||i==k)continue; 50 if(f[i][k]+f[k][j]<f[i][j])51 {52 f[i][j]=f[i][k]+f[k][j];53 g[i][j]=g[i][k]*g[k][j];54 }55 else if(f[i][k]+f[k][j]==f[i][j])g[i][j]+=g[i][k]*g[k][j];56 }57 for1(i,n)58 {59 double ans=0; 60 for1(j,n)61 for1(k,n)62 if(j!=i&&k!=i&&j!=k&&f[j][i]+f[i][k]==f[j][k])63 ans+=double(g[j][i]*g[i][k])/double(g[j][k]);64 printf("%.3lf\n",ans); 65 } 66 return 0;67 }
BZOJ1491: [NOI2007]社交网络