Warning: error_log(/data/www/wwwroot/hmttv.cn/caches/error_log.php): failed to open stream: Permission denied in /data/www/wwwroot/hmttv.cn/phpcms/libs/functions/global.func.php on line 537 Warning: error_log(/data/www/wwwroot/hmttv.cn/caches/error_log.php): failed to open stream: Permission denied in /data/www/wwwroot/hmttv.cn/phpcms/libs/functions/global.func.php on line 537 亚洲影院在线观看,2020国产成人久久精品,好男人社区资源www在线播放 

      

        

          



          
	
          
		
          
			
			
          
				
          整合營(yíng)銷(xiāo)服務(wù)商
          
				
          電腦端+手機(jī)端+微信端=數(shù)據(jù)同步管理
          
			
          
			
          				
				
          免費(fèi)咨詢熱線：
          			
			
          
		
          
	
          
		
	
	
	

          


          
	

          

 

          
  
          
    
          
      
          
        
          [kuangbin帶你飛]專題六最小生成樹(shù)
          
        
           
          
	
	
          
		
          題目鏈接：POJ-1287
          

          題目描述：
          

          您被分配設(shè)計(jì)廣泛區(qū)域中某些點(diǎn)之間的網(wǎng)絡(luò)連接。您將獲得該區(qū)域中的一組點(diǎn)，以及可連接成對(duì)點(diǎn)的電纜的一組可能路線。對(duì)于兩點(diǎn)之間的每條可能路線，您將獲得連接該路線上的點(diǎn)所需的電纜長(zhǎng)度。請(qǐng)注意，在兩個(gè)給定點(diǎn)之間可能存在許多可能的路徑。假設(shè)給定的可能路線（直接或間接）連接該區(qū)域中的每?jī)蓚€(gè)點(diǎn)。
          

          您的任務(wù)是為該區(qū)域設(shè)計(jì)網(wǎng)絡(luò)，以便在每?jī)蓚€(gè)點(diǎn)之間存在連接（直接或間接）（即，所有點(diǎn)都是互連的，但不一定是通過(guò)直接電纜），并且總長(zhǎng)度為用過(guò)的電纜很少。
          

          思路
          

          Prim算法：
          

          Prim算法就是定義mat用來(lái)存圖，dist數(shù)組用來(lái)存每個(gè)點(diǎn)到最小生成樹(shù)的最短距離，vis數(shù)組標(biāo)記此點(diǎn)是否已經(jīng)在最小生成樹(shù)中了（防止出現(xiàn)環(huán)）。
          

          實(shí)際操作就是先隨便把一個(gè)點(diǎn)加入到生成樹(shù)里（一般是第一個(gè)點(diǎn)），然后尋找與該點(diǎn)距離最短的點(diǎn)并加入，然后在尋找與1,2點(diǎn)相連最短的點(diǎn)，并加入到生成樹(shù)中，就這樣不斷的加下去，直到加入的點(diǎn)數(shù)與原圖一致終止；
          

          可以自己手動(dòng)模仿一下過(guò)程，其實(shí)還是好理解的！
          

          ##易錯(cuò)點(diǎn)
          

          1.每次加入前確保加入的權(quán)值比之前加入的權(quán)值要小，否則不加入；
          

          如 第一次 給出 1-2邊的權(quán)值為3， 然后某次加邊操作說(shuō) 1-2邊權(quán)值為10， 這時(shí)候我們保留第一次的權(quán)值（保留權(quán)值較小的那次）
          

          2.題意說(shuō)是邊可能無(wú)限，那么大概不能用Kruskal算法來(lái)做；Prim算法用來(lái)存頂點(diǎn)，而Kruskal算法用來(lái)存邊，當(dāng)邊很多或者不確定是，我們可能無(wú)法用Kruskal算法來(lái)做（當(dāng)然，現(xiàn)在2018年10月9日16:39:24可能還是不能做的，以后說(shuō)不定也可以做）
          

          代碼:
          

          Prim算法：
          

          #include 
#include 
using namespace std;
#define MAX 5050
#define INF 0x3f3f3f3f
int mat[MAX][MAX], vis[MAX], dist[MAX];
void init(int n)
{
    for(int i = 1; i<=n; i++)
    {
        for(int j = 1; j<=n; j++)
        {
            mat[i][j] = INF;
        }
        dist[i] = INF;
    }
}
void Union(int x, int y, int val)
{
    if(val < mat[x][y])
    {
        mat[x][y] = mat[y][x] = val;
    }
}
int Prim(int n)
{
    int sum = 0;
    dist[1] = 0;
    for(int i = 1; i<=n; i++)
    {
        int min_dist = INF, min_vertex;
        for(int j = 1; j<=n; j++)
        {
            if(!vis[j] && dist[j] < min_dist)
            {
                min_dist = dist[j];
                min_vertex = j;
            }
        }
        vis[min_vertex] = 1;
        sum += min_dist;
        for(int j = 1; j<=n; j++)
        {
            if(!vis[j] && mat[min_vertex][j] < dist[j])
            {
                dist[j] = mat[min_vertex][j];
            }
        }
    }
    return sum;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    while(cin >> n, n != 0)
    {
        cin >> m;
        init(n);
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i<m; i++)
        {
            int x, y, val;
            cin >> x >> y >> val;
            Union(x, y, val);
        }
        cout << Prim(n) << endl;
    }
    return 0;
}

          	
          
	
	

          

          

 
          
        
        
		  
      
          
      
      
          
    
          
  
          

          



 


			
		





          
  
          
    
  
          

          

          
	
          
		
		
		
          
	
          


          
 

 







主站蜘蛛池模板：
无码人妻精品一区二区三区在线|
国产成人一区二区精品非洲|
日本一道高清一区二区三区|
一区二区三区AV高清免费波多
|
2018高清国产一区二区三区|
精品一区二区91|
中文字幕av人妻少妇一区二区|
国产精品成人国产乱一区|
精品无人区一区二区三区在线|
一区二区网站在线观看|
国产精品视频无圣光一区|
亚洲国产精品无码第一区二区三区
|
99精品久久精品一区二区|
日韩成人一区ftp在线播放|
精品人妻码一区二区三区|
无码一区二区三区免费|
亚洲一区电影在线观看|
久久久久人妻一区精品色|
久久久久成人精品一区二区|
中文字幕日本精品一区二区三区|
亚洲AV无码一区二区三区在线观看
|
亚洲一区在线免费观看|
极品人妻少妇一区二区三区|
亚洲AV日韩综合一区尤物|
国产一区二区三区播放心情潘金莲
|
国产成人久久一区二区三区|
精品伦精品一区二区三区视频|
亚洲爆乳精品无码一区二区|
日韩精品一区二区三区中文3d|
国产福利电影一区二区三区久久久久成人精品综合
|
香蕉久久一区二区不卡无毒影院|
亚洲一区爱区精品无码|
亚洲av乱码一区二区三区|
国产精品一区二区四区|
风间由美性色一区二区三区|
亚洲色无码专区一区|
国产成人精品一区二区三区无码|
国产日韩精品视频一区二区三区|
波多野结衣中文字幕一区|
日本一区二区在线|
国产91精品一区二区麻豆亚洲|