日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

國內最全IT社區平臺 聯系我們 | 收藏本站
阿里云優惠2
您當前位置:首頁 > php開源 > php教程 > POJ 1502 MPI Maelstrom (Dijkstra算法+輸入處理)

POJ 1502 MPI Maelstrom (Dijkstra算法+輸入處理)

來源:程序員人生   發布時間:2015-01-21 08:39:52 閱讀次數:3541次

MPI Maelstrom
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 5712   Accepted: 3553

Description

BIT has recently taken delivery of their new supercomputer, a 32 processor Apollo Odyssey distributed shared memory machine with a hierarchical communication subsystem. Valentine McKee's research advisor, Jack Swigert, has asked her to benchmark the new system. 
``Since the Apollo is a distributed shared memory machine, memory access and communication times are not uniform,'' Valentine told Swigert. ``Communication is fast between processors that share the same memory subsystem, but it is slower between processors that are not on the same subsystem. Communication between the Apollo and machines in our lab is slower yet.'' 

``How is Apollo's port of the Message Passing Interface (MPI) working out?'' Swigert asked. 

``Not so well,'' Valentine replied. ``To do a broadcast of a message from one processor to all the other n⑴ processors, they just do a sequence of n⑴ sends. That really serializes things and kills the performance.'' 

``Is there anything you can do to fix that?'' 

``Yes,'' smiled Valentine. ``There is. Once the first processor has sent the message to another, those two can then send messages to two other hosts at the same time. Then there will be four hosts that can send, and so on.''

``Ah, so you can do the broadcast as a binary tree!'' 

``Not really a binary tree -- there are some particular features of our network that we should exploit. The interface cards we have allow each processor to simultaneously send messages to any number of the other processors connected to it. However, the messages don't necessarily arrive at the destinations at the same time -- there is a communication cost involved. In general, we need to take into account the communication costs for each link in our network topologies and plan accordingly to minimize the total time required to do a broadcast.''

Input

The input will describe the topology of a network connecting n processors. The first line of the input will be n, the number of processors, such that 1 <= n <= 100. 

The rest of the input defines an adjacency matrix, A. The adjacency matrix is square and of size n x n. Each of its entries will be either an integer or the character x. The value of A(i,j) indicates the expense of sending a message directly from node i to node j. A value of x for A(i,j) indicates that a message cannot be sent directly from node i to node j. 

Note that for a node to send a message to itself does not require network communication, so A(i,i) = 0 for 1 <= i <= n. Also, you may assume that the network is undirected (messages can go in either direction with equal overhead), so that A(i,j) = A(j,i). Thus only the entries on the (strictly) lower triangular portion of A will be supplied. 

The input to your program will be the lower triangular section of A. That is, the second line of input will contain one entry, A(2,1). The next line will contain two entries, A(3,1) and A(3,2), and so on.

Output

Your program should output the minimum communication time required to broadcast a message from the first processor to all the other processors.

Sample Input

5 50 30 5 100 20 50 10 x x 10

Sample Output

35

Source

East Central North America 1996



題意:信息傳輸,總共有n個傳輸機,先要從1號傳輸機向其余n⑴個傳輸機傳輸數據,傳輸需要時間,給出1個嚴格的下3角(其實就是對角線之下的不包括對角線的部份)時間矩陣,a[i][j]代表從i向j傳輸數據需要的時間,并規定數據傳輸之間并沒有影響,即第1個傳輸機可以同時向其余傳輸機傳輸數據。求所有傳輸任務所需的最短時間。


解析:1個很裸的單源最短路,并且按題意可知邊不可能為負值,那末直接用Dijkstra便可。求編號為1的傳輸機到所有傳輸機的最短傳輸時間以后,那末所有最短時間中的最大值即為完成傳輸任務的最短時間。

PS:這題的讀入還是很惡心的,由于有x的存在,所以我們就需要把數字當做字符串去讀,然后再將其轉成int。

切記:無窮大不能開太大啊了,開大了如果超過數據類型的范圍的話,就會算出來負數,結果固然也就不對了。



AC代碼:

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define INF 123456789 #define MAXN 100 + 2 int V, E; int w[MAXN][MAXN]; int vis[MAXN], dis[MAXN]; int input(){ //手寫讀入函數 char str[10]; scanf("%s", &str); if(!strcmp(str, "x")) return INF; //'x'代表兩點無路徑,用INF表示 else{ int ans = 0; int len = strlen(str); for(int i=0; i<len; i++){ ans = ans*10 + str[i] - '0'; } return ans; } } void dijkstra(){ //dijkstra函數 memset(vis, 0, sizeof(vis)); //預處理 for(int i=1; i<=V; i++) dis[i] = (i == 1 ? 0 : INF); for(int i=1; i<=V; i++){ //dijkstra int x, m = INF; for(int y=1; y<=V; y++) if(!vis[y] && dis[y] <= m){ x = y; m = dis[x]; } vis[x] = 1; for(int y=1; y<=V ;y++) dis[y] = min(dis[y], dis[x] + w[x][y]); //松弛操作 } } int main(){ #ifdef sxk freopen("in.txt", "r", stdin); //此舉為調試語句,可疏忽 #endif // sxk while(scanf("%d", &V)!=EOF){ for(int i=1; i<=V; i++) //讀入數據 for(int j=1; j<=i; j++){ if(i == j) w[i][j] = 0; else w[j][i] = w[i][j] = input(); } dijkstra(); //處理 int ans = -INF; //找其中的最大跳躍高度 for(int i=1; i<=V; i++){ if(ans < dis[i]) ans = dis[i]; } printf("%d ", ans); } return 0; }




生活不易,碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生
------分隔線----------------------------
分享到:
------分隔線----------------------------
關閉
程序員人生
主站蜘蛛池模板: 中文字幕免费在线视频 | 中文字幕一区二区三区在线视频 | 免费性爱视频 | 国产一区二区高清 | 日韩 综合 | 欧美日韩国产91 | 日韩精品视频久久 | av网站在线播放 | 国产精品成人一区 | 国产人妖视频 | 国产中文字幕av | 免费国产精品视频 | av一区免费 | 国产3区| 欧美精品a∨在线观看不卡 黄色av免费 | 亚洲精品在线视频 | 99国产一区 | 能看的av | 国产成人99久久亚洲综合精品 | 国产激情美女久久久久久吹潮 | 成人h视频在线观看 | 国产美女一区二区 | 中文字幕+乱码+中文字 | 久久99精品久久久久久 | 日韩欧美一区二区三区免费观看 | 久久高清精品 | 国产精品久久国产三级国电话系列 | 91精品啪在线观看国产81旧版 | 亚洲一区二区成人 | 青青av | 精品国产99久久久久久宅男i | 亚洲一级视频在线 | 视频精品久久 | 精品久久久久久久久久久下田 | 91 久久 | 国产精品久久久久久久久久免费 | 国产精品黄色小视频 | 久久国产精品久久 | 久久免费国产视频 | 一级不卡| 中文字幕自拍 |