查看: 847|回復: 0

[UVa] 11015 - 05-2 Rendezvous

[複製鏈接]
  • TA的每日心情
    鬱悶
    2015-5-15 22:38
  • 簽到天數: 33 天

    [LV.5]常住居民I

    75

    主題

    302

    帖子

    766

    積分

    版主

    TFcis - 105 附設監工官

    Rank: 7Rank: 7Rank: 7

    積分
    766

    台南一中資訊社程式設計達人 - 2014

    發表於 2015-3-18 22:33:02 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    x
    本帖最後由 jd3 於 2015-3-19 13:22 編輯


    http://uva.onlinejudge.org/index ... roblem&problem=1956


    題意:
    大致上是說要找到一個點讓所有人點到那裏的總距離最短


    想法:
    嗯......一臉最短路
    只是要算的是各點到那裏的最短距離總和
    再從中找最小的
    沒想到什麼特別的解法,就用最短路的演算法寫吧



    解法:

    法1:
    直觀的枚舉每個點
    對每個點做一次 Dijkstra 算總和
    時間複雜度 O(V*E*log(E) )


    法2:
    其實只要做一次 Floyd-Warshall 得到全點對最短距離 → O(V^3)
    再用 O(V^2) 枚舉所有點當目的地的情況就OK了
    總複雜度 = O(V^3)


    比較:
    因為 E 最多是 V^2 級別
    所以法1可以換算成 O(V^3 * log(V^2))
    所以從複雜度來看法2比較快



    能簡則簡
    F-W好寫很多
    全點對能用F-W 就不要用 Dijkstra
    有時候複雜度會爛掉owo

    [C++] 純文本查看 復制代碼
    #include<iostream>
    #include<cstdio>
    
    #define INF 1000000000
    
    using namespace std;
    
    int n,m;
    int dist[30][30];
    string name[100];
    
    void FW()
    {
    	for(int j = 1 ; j <= n ; j++)
    		for(int i = 1 ; i <= n ; i++)
    			for(int k = 1 ; k <= n ; k++)
    				dist[i][k] = min(dist[i][k], dist[i][j]+dist[j][k]);
    }
    
    int main()
    {
    	
    	for(int time = 1 ; ; time++)
    	{
    		cin >> n >> m;
    		
    		if(n==0 && m==0)
    			return 0;
    		int a,b,w;
    		for(int i = 1 ; i <= n ; i++)
    			cin >> name[i];
    			
    		for(int i = 1 ; i <= n ; i++)
    			for(int j = 1 ; j <= n ; j++)
    				dist[i][j] = INF;
    		for(int i = 1 ; i <= n ; i++)
    			dist[i][i] = 0;
    		for(int i = 1 ; i <= m ; i++)
    		{
    			cin >> a >> b >> w;
    			if(w < dist[a][b])
    			{
    				dist[a][b] = w;
    				dist[b][a] = w;
    			}
    		}
    		
    		FW();
    		
    		int ans, min_sum = INF;
    		for(int i = 1 ; i <= n ; i++)
    		{
    			int sum = 0;
    			for(int j = 1 ; j <= n ; j++)
    			{
    				sum += dist[i][j];
    			//	printf("%d %d = %d\n",i,j,dist[i][j]);
    			}
    			
    			
    		//	cout << "sum = " << sum << endl;
    			
    			if(sum < min_sum)
    			{
    				min_sum = sum;
    				ans = i;
    			}
    		}
    		
    		cout << "Case #" << time << " : " << name[ans] << endl;
    	}
    	
    	return 0;
    }
    

    <這是個人簽名欄位>
    回復

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表