NOI 2007 社交网络

这是NOI2007最简单的一道题了吧，考察的是细心。由于要求每对顶点的最短路径，可以用floyd求。定义path[i][j]为从i到j的最短路径的条数，floyd松弛时，要更新path[i][j] = path[i][k] * path[k][j]，如果遇到dist[i][k] + dist[k][j] == dist[i][j]这样的情况，要令path[i][j] += path[i][k] * path[k][j]。

接下来就是根据定义求每个顶点重要程度值I了，其中C(s,t)=path[s][t]，根据乘法原理，过v的最短路径条数C(s,t,v)=path[s][v] * path[v][t]。求出I值输出即可。注意最短路径数目不超过10^10，所以要用到64位整型数来记录路径条数。

/* 
 * Problem: NOI2007 network
 * Author: Guo Jiabao
 * Time: 2009.6.5 9:54
 * State: Solved
 * Memo: 最短路径
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=101;
const double INF=1e20;
int N,M;
double dist[MAXN][MAXN],path[MAXN][MAXN];
void init()
{
	int i,j,a,b,c;
	freopen("network.in","r",stdin);
	freopen("network.out","w",stdout);
	scanf("%d%d",&N,&M);
	for (i=1;i<=N;i++)
	{
		for (j=1;j<=N;j++)
		{
			dist[i][j]=INF;
			path[i][j]=1;
		}
		dist[i][i]=0;
	}
	for (i=1;i<=M;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		dist[a][b]=dist[b][a]=c;
	}
}
void floyd()
{
	int i,j,k;
	double I;
	for (k=1;k<=N;k++)
		for (i=1;i<=N;i++)
			for (j=1;j<=N;j++)
			{
				if (i==k || k==j || i==j) continue;
				if (dist[i][k] + dist[k][j] < dist[i][j])
				{
					dist[i][j] = dist[i][k] + dist[k][j];
					path[i][j] = path[i][k] * path[k][j];
				}
				else if (dist[i][k] + dist[k][j] == dist[i][j])
					path[i][j] += path[i][k] * path[k][j];
			}
	for (k=1;k<=N;k++)
	{
		I=0;
		for (i=1;i<=N;i++)
			for (j=1;j<=N;j++)
				if (i!=k && j!=k && i!=j && dist[i][k] + dist[k][j] == dist[i][j])
					I += path[i][k] * path[k][j] / path[i][j];
		printf("%.3lfn",I);
	}
}
int main()
{
	init();
	floyd();
	return 0;
}

<h2><span class="mw-headline">社交网络 </span></h2>

【问题描述】

在社交网络（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的最短路的数目；则定义

<a class="image" title="Image:Network2007 1.jpg" href="http://www.ruvtex.cn/wiki/Image:Network2007_1.jpg"><img src="http://www.ruvtex.cn/mw/images/e/e4/Network2007_1.jpg" alt="Image:Network2007 1.jpg" width="330" height="114" /></a>

为结点v在社交网络中的重要程度。

为了使I(v)和Cs,t(v)有意义，我们规定需要处理的社交网络都是连通的无向图，即任意两个结点之间都有一条有限长度的最短路径。

现在给出这样一幅描述社交网络s的加权无向图，请你求出每一个结点的重要程度。

【输入文件】

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

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

【输出文件】

输出文件包括n行，每行一个实数，精确到小数点后3位。第i行的实数表示结点i在社交网络中的重要程度。

【样例输入】
<pre>4 4
1 2 1
2 3 1
3 4 1
4 1 1</pre>
【样例输出】
<pre>1.000
1.000
1.000
1.000</pre>
【样例说明】

社交网络如下图所示。

<a class="image" title="Image:Network2007 2.jpg" href="http://www.ruvtex.cn/wiki/Image:Network2007_2.jpg"><img src="http://www.ruvtex.cn/mw/images/1/1a/Network2007_2.jpg" alt="Image:Network2007 2.jpg" width="450" height="334" /></a>

对于1号结点而言，只有2号到4号结点和4号到2号结点的最短路经过1号结点，而2号结点和4号结点之间的最短路又有2条。因而根据定义，1号结点的重要程度计算为1/2+1/2=1。由于图的对称性，其他三个结点的重要程度也都是1。

【评分方法】

本题没有部分分，仅当你的程序计算得出的各个结点的重要程度与标准输出相差不超过0.001时，才能得到测试点的满分，否则不得分。

【数据规模和约定】

50%的数据中：n ≤10，m ≤45
100%的数据中：n ≤100，m ≤4 500，任意一条边的权值c是正整数，满足：1 ≤c ≤1 000。
所有数据中保证给出的无向图连通，且任意两个结点之间的最短路径数目不超过10^10。

上次修改时间 2017-05-22

相关日志