首頁‎ > ‎C++演算法解題(1)‎ > ‎

uva-821-PageHopping-Floyd

出處 https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=762

解題策略
uva-821-PageHopping,Floyd演算法找最短路徑,網頁與網頁距離為1,G[][]為很大的值,才會更新, G[i][i]=0,避免G[i][i]更新。
也可以使用BFS演算法解題。

待完成或參考程式碼
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/*
Floyd演算法找最短路徑,網頁與網頁距離為1,
G[][]為很大的值,才會更新, G[i][i]=0,避免G[i][i]更新。
也可以使用BFS演算法解題。
執行時間:0.048s 
*/
#include <cstdio>
#include <cstring>
#include <deque>
#include <queue>
#include <map>
#include <algorithm>
#define MAX 110
using namespace std;
int G[MAX][MAX];
map<int,int> nmap;	//使用map將int轉成數字,數字從0開始編號 
void memNum(int num){	//將num轉成數字,數字從0開始編號 
	if (nmap.find(num)==nmap.end()){
		int s=nmap.size();
		nmap[num]=s;
	}
} 
void init(){
	nmap.clear();
	memset(G,0x3f,sizeof(G));
	for(int i=0;i<MAX;i++) G[i][i]=0;	//G[i][i]不用計算網頁的次序 
}
int main(){
  int x,y,cnt,ncase=1;
  while (scanf("%d%d",&x,&y)==2){
  	if ((x==0)&&(y==0)) break;
  	init();
  	memNum(x);//將x加入map
  	memNum(y);//將y加入map
  	G[nmap[x]][nmap[y]]=1;//建立圖,將網頁編號改成0開始的連續整數 
  	while (scanf("%d%d",&x,&y)==2){
  		if ((x==0)&&(y==0)) break;
  		memNum(x);//將x加入map
  		memNum(y);//將y加入map
  		G[nmap[x]][nmap[y]]=1;//建立圖,將網頁編號改成0開始的連續整數
  	}
  	cnt=0;
  	int s=nmap.size();
  	for(int k=0;k<s;k++){//Floyd演算法 
  		for(int i=0;i<s;i++){
  			for(int j=0;j<s;j++){
  				G[i][j]=min(G[i][j],G[i][k]+G[k][j]);
				}  		
			}	  		
		}
		for(int i=0;i<s;i++){
  		for(int j=0;j<s;j++){
  			if (G[i][j]!=0x3f3f3f3f) cnt+=G[i][j];
			}  		
		}	  	
    printf("Case %d: average length between pages = %.3lf clicks\n",ncase++,(double)cnt/(s*(s-1)));
  }     
}

Comments