NOI 2007 社交網絡

本文正體字版由OpenCC轉換

這是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

相關日誌